Regularized Softmax Deep Multi-Agent Q-Learning
Authors: Ling Pan
Tabish Rashid
Bei Peng
Longbo Huang
Shimon Whiteson
Venue: NeurIPS 2021 Poster (2021)
Keywords: Multi-Agent Reinforcement Learning
MARL
Value Factorization
Overestimation

Abstract: Tackling overestimation in $Q$-learning is an important problem that has been extensively studied in single-agent reinforcement learning, but has received comparatively little attention in the multi-agent setting. In this work, we empirically demonstrate that QMIX, a popular $Q$-learning algorithm for cooperative multi-agent reinforcement learning (MARL), suffers from a more severe overestimation in practice than previously acknowledged, and is not mitigated by existing approaches. We rectify this with a novel regularization-based update scheme that penalizes large joint action-values that deviate from a baseline and demonstrate its effectiveness in stabilizing learning. Furthermore, we propose to employ a softmax operator, which we efficiently approximate in a novel way in the multi-agent setting, to further reduce the potential overestimation bias. Our approach, Regularized Softmax (RES) Deep Multi-Agent $Q$-Learning, is general and can be applied to any $Q$-learning based MARL algorithm. We demonstrate that, when applied to QMIX, RES avoids severe overestimation and significantly improves performance, yielding state-of-the-art results in a variety of cooperative multi-agent tasks, including the challenging StarCraft II micromanagement benchmarks.

Regularized Softmax Deep Multi-Agent Q-Learning
Ling Pan', Tabish Rashid?, Bei Peng", Huang', Shimon Whiteson
Institute for Interdisciplinary Information Sciences, Tsinghua University
p1170mails. tsinghua. eedinghaaedd...... en, Longbohuang@bssingua.. edu.
University of Oxford
tabish.rashide ox. ac. shimon. whi whitesoncss. ox..eeooo... ac
University of Liverpool bei b.i. www.ppeeeivrrppooloo acc.lll.cuuu ac.uk
Abstract
Tackling overestimation in Q-learnig is an important problem that has been extensively studied in single-agent reinforcement learning, but has received com- paratively little attention in the multi-agent setting. In this work, we empirically demonstrate that QMIX, popular Q-learning algorithm for cooperative multi- agent reinforcement learning (MARL), suffers from a more severe overestimation in practice than previously acknowledged, and ís not mitigated by existing ap- proaches. We rectify this with a novel regularization-be based update scheme that penalizes large joint action-values that deviate from baseline and demonstrate its effectiveness stabilizing learning. Furthermore, we propose to employ a softmax operator, which efficiently approximate in novel way in the multi- agent setting, to further reduce the potential ovcrestimation bias. Our approach, Regularized Softmax (RES) Deep Multi-Agent Q-Learning, is general and can be applied to any Q-learning based MARL algorithm. We demonstrate that, when applied to QMIX, RES avoids severe overestimation and significantly improves performance, yielding state-of-the-arr results in a variety of cooperative multi-agent tasks, including the challenging StarCraft II micromanagement benchmarks.
Introduction
In recent years, multi-agent reinforcement learning (MARL) has achieved significant progress under the popular centralized training with decentralized execution (CTDE) paradigm [2
4
20
15
In
CTDE, the agents must learn decentralized policies that execution time they can act based on only local observations, but the training itself is centralized, with access to global information. A critical challenge this setting how to represent and learn the joint action-value function
In learning the value function, overestimation is an important challenge that stems from the max operator (34] typically used in the bootstrapping target. Specifically, the max operator in Qllearnin [39] approximates the maximum expected value with the maximum estimated value. This can lead to overestimation as E [max; X;] 2 max; EE [X,] due noise (34 where X; is a random variable representing the Q-value of action i given a state. This overestimation error can accumulate during learning, lead to sub-optimal policy updates and behaviors, and hurt the performance of both value- based [37 2 32
[6] and actor-critic algorithms (8), and has been widely studied in the single-agent domain. However, overestimation can be even more severe in the multi-agent setting. For example, suppose there are n agents, each agent has K actions, and the Q-value for each action given state is independently drawn from a uniform distribution (O, 1). Then, max; E [X,] is 1 while I. [max, X,) R
2
is K=+ which quickly approaches 1 (the maximum value of X2) as the size of the joint action space
Work done while University of Oxford.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

increases exponentially with the number of agents. Nonetheless, this problem has received much less attention in MARL.
QMIX 29 is a popular CTDE deep multi-agent Q-learning algorithm for cooperative MARL.. It combines the agent-wisst wise utility functions Qa into the joint action-value function Qtot. via monotonic mixing network to ensure consistent value factorization. Due to its superior performance, there have been many recent efforts to improve QMIX's representation capability [31 27 38]. However, the overestimation problem of the joint-action Q-function Qtor can be exacerbated in QMIX due not only to overestimation in agents' Qe but also the non- non-linear monotonic mixing network. Despite this, the role of overestimation in limiting its performance has been largely overlooked.
In this paper, show empirically that over- estimation in deep multi-agent Q-learning is more severe than previously acknowledged and can lead to divergent learning behavior in prac- tice. In particular, consider double estimators, which can successfully reduce overestimation bias in the single-agent domain [37 g
Reeeyeepeyy Prpalca decsption
Covert commantiaaion
Al-
60
1.2 10 3.0
1.10
though QMIX applies Double DQN 37 to es-
timate the value function (as mentioned in Ap-
Figure I: Normalized performance (left) and value estimations in log scale (right) of QMIX in the multi-agent particle environments. Value estima- tions grow unbounded (right) and lead to catas- trophic performance degradation (left).
pendix D.3 in [28] and open-source PyMARL [30] implementationn), we find that it is ineffec- tive in deep multi-agent Q-learning. As shown in Figure [ (same experimental setup as in Sec- tion 5). value estimates of the joint-action Q-function can increase without bound in tasks from the multi-agent particle framework (18), yielding catastrophic performance degradation. Our experiments show that surprisingly, even applying Clipped Double Q-learning (a key technique from a state- of-the-art TD3 [8 algorithm) to the multi-agent setting does not resolve the severe overestimation bias in the joint-action Q-function. Therefore, alleviating overestimation in MARL is a particularly important and challenging problem.
To tackle this issue, we propose a novel update scheme that penalizes large joint-action Q-values. Our key idea to introduce a regularizer in the Bellman loss. direct penalty on the magnitude of joint-action Q-values can result in a large estimation bias and hurt performance. Instead, to better trade off learning efficiency and stability, we introduce a baseline into the penalty, thereby constraining the joint-action Q-values to not deviate too much from this baseline. Specifically, we use the discounted return as the baseline. By regularizing towards a baseline, we stabilize learning and effectively avoid the unbounded growth in our value estimates.
However, regularization is not enough to fully avoid overestimation bias in the joint-action Q- function due to the max operator in the target's value estimate (34). To this end, we propose to employ a softmax operator, which has been shown to efficiently improve value estimates in the single-agent setting [32 26 25 Unfortunately, direct application of the softmax operator is often too computationally expensive in the multi-agent case, due to the exponentially-siien joint action space. We therefore propose novel method that provides an efficient and reliable approximation to the softmax operator based on a joint action subspace, where the gap between our approximation and its direct computation converges to 0 at exponential rate with respect to its inverse temperature parameter. The computational complexity of our approximation scales only linearly in the number of agents, as opposed to exponentially for the original softmax operator. We show that our softmax operator can further improve the value estimates in our experiments. We refer to our method as RES (Regularized Softmax) deep multi- agent Q-learning, which utilizes the discounted return-based regularization and our approximate softmax operator.
To validate RES, we first prove that it can reduce the overestimation bias of QMIX. Next, we conduct extensive experiments in the multi-agent particle tasks 18). and show that RES simultaneously enables stable learning, avoids severe overestimation when applied to QMIX, and achieves of the-art performance. RES is not tied to QMIX and can significantly improve the performance and stability of other deep multi-agent Q-learning algorithms. e.g., Weighted-QMIX (27) and QPLEX [3), demonstrating its versatility. Finally, to demonstrate its ability to scale to more complex scenarios, we evaluate it set of challenging StarCraft II micromanagement tasks (30.. Results show that RES- RES-Q provides a consistent improvement over QMIX in all scenarios tested.
2

---

2 Background
Decentralized partially observable Markov decision process (Dec-POMDP). A fully coop- erative multi-agent task can be formulated as Dec-POMDP 12 represented by tuple U, U, r. Z, O) where A = (1, ...,.. n denotes the finite set of agents, $ E S is the global state, and E [0, 1) is the discount factor. The action space for an agent is U with size K. At each timestep, each agent a E A receives an observation Z E Z from the observation function O(s, a) due to partial observability, and chooses an action un E U, which forms a joint action E U = U This leads to a transition to the next state s' ~ P(s' [s, u)) and a joint reward r(8, u). We assume that the reward function is bounded [35, i.e., (n(s, u)) I Rmax. Each agent has an action-observation history To E = (Z x U)", based on which it constructs a policy n. (ue (Ta). The goal is to find an optimal joint policy π (TI,..., Tn), whose joint action-value function is Q Ut)
E r'rt+o).
extends deep Q- learning [39]. popular value-based method for learning optimal action values, to the multi-agent setting. Given transitions (s, u. r. sampled from the experience replay buffer B. its objective is to minimize the mean squared error loss L(#) on the
Deep multi-agent Q-learning. Deep multi-agent Q-learning
33
29
38
(TD) error 5 = y Qrae (s, u), where y = r + Y max,'' Qtar(s', u²) is the target value, and Qtot is the target network for the joint- action Q-function that is periodically copied from Q Parameters of Qtor are denoted by 0 that are updated by 0' = Ve (0), where a is the learning rate. To mitigate the overestimation bias from the max operator in the target's value estimate [34), Double DQN [37 [ estimates the target value as y = r + QQ (s', arg max,'' Qtor u')) which decouples action selection and evaluation.
agents are trained in a centralized way with access the overall oobtevttibsrvation history and global state during training, but during execution have access only to their own local action- cisoonn-bsvvvttonn histories. The individual globall-ooa--anon max (IGM) property BI a popular concept realize efficient CTDE as in Eq. (1) where Qtat and Qa denote the joint-action Q-function and agent-wiss utilities respectively.
Centralized training with decentralized execution (CTDE). In CTDE 23 15
arg max Qrat u) = arg max Q1 u1), ... arg max Qr (s, un))
(1)
The IGM property enables efficient decentralized execution, which ensures the consistency between greedy action selection in the local and joint Q-values. QMIX (29] is a popular CTDE method that combines Qa into Qtot via non-linear monotonie function fa that is state-dependent in Eq. (2) To satisfy the IGM property, fa is constrained to be monotonic in Qa. i... 0fz 2 0, Va A. which is achieved by enforcing non- non-negative weights in fs.
JQ
(s, u) = (s, Q.((,,
(2)
3 Overestimation in QMIX
In this section, we show empirically that the overestimation problem for deep multi-agent Q-learning can be more severe in practice than previously acknowledged. In particular, we demonstrate that state-of- the-art methods for tackling this issue in the single-agent domain can fail in our multi-agent setting.
25
Bntum
10
OPER
We investigate the behavior of QMIX in the predator-prey task from the multi-agent particle environments 18), where slower predators need to coordinate to capture faster prey to solve the task. A detailed description of the task is included in Appendix E.1.1. We consider a fully cooperative setting where the prey is pre-trained by MADDPG [8] to avoid capture by the predators, and the predators need to learn to cooperate with each other in order to surround and capture the prey.
OMEX (C04)
100 4.6 Ep Episode (4127)
25
Figure 2: Return of QMIX and its variants in the predator-prey environment.
Figures 2 and 3 a) show the performance of QMIX and its estimated values of the joint-action fuuectio during training respectively. QMIX suffers from catastrophic performance degradation and severe overestimation bias, where its value estimates grow without bound. Figures and ac) illustrate the mean agent-wise utilities Qa and their gradients as./aQ, over agents respectively. We see that for QMIX, the gradients af./OQ, increase rapidly and continuously during learning. Figure 3(d) shows the learned weight (matrix) of the monotonic mixing network fa. The weights similarly
3

---

grow larger during training and further amplify the overestimation in each Qa when computing Qrot- leading to a severely overestimated joint-action Q-function that continues to grow without bound.
To reduce overestimation, Ackermann et al. [ extend the state-of-the-art TD3 algorithm (8. which addresses overestimation in the single-agent case, to the multi-agent setting. We obtain QMIX (CDQ) by applying the key Clipped Double Q-learning technique from TD3 [8] to per-agent utilities in 3)) (), QMIX (CDQ) slows the increase of agent-wise utilities. However, Figure a shows that it still does not eliminate the severe overestimation bias in the joint-action Q-function, and subsequently suffers a performance degradation as shown in Figure 2 This is due to the gradients of the monotonic mixing network, 0f./OQu. which still continuously increase as shown Figure ce), leading to the large and increasing value estimates in Figure B().
QMIX for value estimation 2 As shown in Figure
GMICK
Ta 183
66-
OMRC Resl
Cleck (C20 Grushagi
40
28-
10
Estvode 20000s
-10
0.4
1.0 1.3
24
0/3
1.0
3.5
24
0.5
3.5
3.5 24
(a)
(b)
(c)
Figure 3: Learning statistics during training in predator-prey. (a) Value estimates in log scale. (b) Of. over agents in log scale. Mean agent-wise utility functions Qo over agents. (c) Mean gradients TQ2 (d) The learned weight (matrix) in the monotonic mixing network fa of QMIX, where a darker color represents a larger value (a detailed description is in Appendix A.1).
Another way to avoid overly large value estimates is to limit the gradients themselves. We propose Gradient Regularization (GradReg) prevent the gradients f from growing too large by regularizing the gradient using a quadratic penalty. Specifically, the loss function of QMIX (GradReg) is defined as ReradReg (0) [sssu,r .')-B [8² + X(0fs/ (00f)//Q.)) where d is the TD error defined in 2 and À is the regularization coefficient. However, although QMIX (GradReg) with a tuned coefficient for the regularizer prevents the gradients from growing overly large during the early stage of learning (FigureBjc B(c)), the wiie utility functions grow larger instead as shown in Figure (bb). This then still leads to a particularly large value estimate shown in Figure combination of both CDQ and GradReg also fails to avoid the problem.
Section
3 (). Finally, direct
From these experiments, we see that even applying the otate-of-the-art TD3 g method from the single-agent literature can fail in our multi-agent setting. addition, it is also insufficient to tackle the problem by regularizing the magnitude of the gradients 0f. These results show that mitigating overestimation in MARL is particularly important and challenging, and requires novel solutions.
Regularized Softmax (RES) Deep Multi-Agent Q-Learning
Our analysis shows that preventing gradients from being large in QMIX (GradReg) and/or utilizing clipped double estimators as in QMIX (CDQ) are not sufficient to prevent overly large value estimates. It is important to note that these methods take an indirect approach to reduce the overestimation of the joint-action Q-value, and as shown do not solve the severe overestimation problem. Therefore, we propose a novel way to directly penalize large joint-action Q-values avoid value estimate explosion.
Directly penalizing large joint-action Q-values can push their values towards 0, yielding a large estimation bias. Instead, we introduce baseline into the penalty to better trade off learning efficiency and stability. Specifically, the new learning objective penalizes joint-action Q-values deviating from a baseline b(s, u). by adding a regularizer to the loss: X (Qtor (s, u) b(s, u))² where we use the mean squared error loss and À is the regularization coefficient. A potential choice for the baseline is the -tseep return, i.c., b(s, u) EN= 7'r,+ + max,' Q u'). Figure/4(a) shows the value estimates of Regularized (RE)- (ME)-QMIX (b = N-step return) using the N-step return as the baseline (with best A). However, as it still involves Qtot, the value estimation can still grow extremely large despite being discounted, yielding estimates that almost coincide with those of QMIX.
Applying CDQ on Quot leads to larger value estimates than applying it on Qa (details are in Appendix A.2).

---

Therefore, we propose to use the discounted return starting from state as the baseline to regularize learning, i... b(s, u) = (, u) = Ex=o 7 for the t-th timestep. The regularized learning objective directly penalizes large joint-action Q-values and allows the value estimates to remain grounded by real data. As shown in Figure aa), RE-QMIX effectively avoids particularly large value estimations and stabilizes learning.
However, while the regularized learning objective is effective in resolving value ex- plosion, it can still overestimate due to the use of the max operator when computing
HR: QNNX /tattinem//-ttt rstar))
QMIX
target value estimates [84] Figure 4[bb
RE-QNIX
50
shows the estimated and true values of RE-
FE FE-0MIX
He CMRX
True 12: 12-0XXX
QMIX (with best )). The estimated val- ues are computed by averaging over 100 states sampled from the replay buffer at each timestep, and we estimate true values by averaging the discounted returns which are obtained by following the greedy pol- icy with respect to the current Qiot starting from the sampled states. As shown in Fig- ure b), although RE-QMIX avoids unbounded growth of its value estimates, it does not fully avoid the overestimation bias, which still estimates the target value according to the max operator (4).
RE-OHI MHoopp reluro
RES-CM
sode (x10P)
Episade (etee)
(b)
Figure 4: Comparison of value estimates in predator-
prey. (a) Value estimation in log scale for QMIX and RE-QMIX with different baselines. (b) True values and estimated values of RE-QMIX and RES-QMIX
To further mitigate overestimation bias in the joint-action Q-function, we adopt the softmax operator, which has shown great potential in reducing overestimation bias in place of the max operator in
single-agent domains [32 26 25). Specifically, the softmax operator is defined in Eq. (3) where
3 0 is the inverse temperature parameter.
(BQcoe(o.u) WEU Ewer Qroeleaa) Qtoe(s, u).
sm (Qror (s.
Σ
(3)
When 3 approaches oo or 0, softmax reduces to the max or mean operator respectively. Unfortunately, computing Eq. (3) in the multi-agent case can be computationally intractable the size of the joint action space grows exponentially with the number of agents. In addition, as the action space in the multi-agent case is much larger than that in the single-agent case, some joint-action Q-value estimates Qtor(8, u) can be unreliable due to a lack of sufficient training. Thus, directly taking them all into consideration for computing the softmax operator in Eq. (3) can result inaccurate value estimates.
We propose a novel method to approximate the computation of the softmax operator efficiently and reliably. Specifically, we first obtain the maximal joint action ú arg max,, Qual (8, u) with respect to Qeae according to the andividual-globll-ne agent a, we consider K joint actions, by changing only agent a's action while keeping the other agents' actions ú fixed. We denote the resulting action set of agent by U, = {[u, úma)(u, E U).
(IGM) property discussed in Section [ Then, for each
Finally, we form joint action subspace Ú = U, U .... UU. where each U, contributes K actions, and use Ú in Eq. 3 for computing the approximate softmax operator. In Theorem we show that the gap between our approximation in U and its direct computation in the joint action space U converges to 0 at an exponential rate with respect to B. The proof can be found in Appendix B.1.
Theorem 1. Let u² and ui' denote the optimal joint actions in U and U Ô with respect to Qior. respectively. The difference between our approximate softmax operator and its direct com- putation in the whole action space satisfies: Vs E S, S.|sm,.0 (Qrorss -)) sm,, (Qroe(s, (s.-)) s
28max
|--
where I - Ú denotes the size of the set U - Ó.
Discussion. Since its computational complexity is linear instead of exponential in the number of agents, our approximation is feasible to compute even when the number of agents grows large, as opposed to the original softmax operator. According to the IGM property, I consists of joint actions that are close to the maximal joint action र. Thus, it it more likely to contain joint actions with more accurate and reliable value estimates, especially when using é-greedy exploration, since they are more likely to be sampled and therefore trained. Due to this reduced reliance on unreliable joint-action Q-values, our approximate softmax operator actually outperforms its counterpart using
5

---

a direct computation in the joint action space U, as well as random sampling scheme, as shown in Section [5.1.3] The full algorithm for our approximate softmax is in Appendix B.2. As shown in Figure 4 b). RES (Regularized Softmax)- -MIX fully addresses the overestimation bias and achieves better value estimates than RE-QMIX?
The loss of Regularized Softmax (RES) Deep Multi-Agent Q-Learning (RES is defined as:
E (e gamg + + (Quor u) - RR R))
(4)
where dams = r 9 9.ú Qiorr (.) Qroe u), and x denotes the coefficient of the regularizer.
To better understand the effectiveness of our method, we provide a theoretical justification that connects the loss function of RES and a new Bellman operator in Theorem 2
Theorem 2. Given the same sample distribution, the update of the RES method is equivalent to the update using [() = ( [V Qtat (8, u))² with learning rate (A + 1)a, which estimates
the target value according to T+ (Quie + AR.(a.))
X+1
X+1
Its proof is in Appendix C. In the special case where À O, it is equivalent to changing the max operator to our approximate softmax in the target value estimation. When O, it be thought of as learning with weighted combination of the 1-step TD target with our approximate softmax and the discounted return, which allows the bootstrapping target remain grounded by real data
Let T be the value estimation operator which estimates the value of the next state s'. From Theorem) we have TQMIX- max Qioe (s', u'), TRE-QMIX max, Qtails' .u''''++ A and TRES-QMIX
A+1
sms.0 (Q (s),)))+ Ae)+ We now analyze the relationship between the value estimation bias of
X+1 these operators in Theorem (the proof in Appendix D), and show that RES- RES-QMIX can reduce the overestimation bias when built upon QMIX. It is also worth noting that since RES is general, it can be readily applied to other deep multi-agent Q-learning algorithms, as investigated in Section [51.4]
Theorem 3. Let B(T)= = [sT( max,'' Qia (s', , u') be the bias of value estimates of T and the true optimal joint-action Q-function Qior. Given the same assumptions as in 137/ for the joint-uction Q-function, where there exists some Vo'e Qioll'' u')sor different joint actions. En (Qro1 (s', uu)) Vi)o(s') O, and TOT Ens (s' w²) (s)( C (C > 0) with Qiot an arbitrary joint-action Q-function, then B(TRES QMIX) S B(TRE.QMIX) S B(TQMIx).
From the proof of Theorem 3 and Figure 4 4a), we find that RE- FM-QMIX reduce the overestimation bias of QMIX following the same standard assumptions in 37 32 In addition, Theorem 3 also shows that the bias of value estimates of RES-QMIX is no larger than that of RE-QMIX, which validates our RES method.
Experiments
We conduct series of experiments in the multi-agent particle tasks 18] to answer: (i) How much can our RES method improve over QMI?? (ii) How does RES EEI- compare against state-of -f-th-rr- methods in performance and value estimates? (iii) How sensitive is RES important hyperparameters and what is the effect of each component? (iv) Can RES be applied to other algorithms? We also evaluate our method on the challenging SMAC benchmark [30] demonstrate its scalability. The
code is publicly available at https: thw.ttgbttttttt/t///ee//gteb..et com www.m/////-/////eeeeeeeeeelleeaa waiiingggggnnaae pan- /ES
5.1 Multi-Agent Particle Environments
The predator-prey (PP) task was introduced in Section Physical deception (PD) involves cooperating agents and 1 adversary, whose goal is to reach a single target landmark from total of two landmarks, while the adversary is unaware of the target. World (W) involves 4 slower agents who must coordinate to catch 2 faster adversaries that desire to eat food. In covert communication
Note that applying the softmax operator on agent-wise wise utilities results in a larger underestimation bias and significantly underperforms RES, a detailed discussion is included in Appendix B.3.
"The result of QMIX with learning rate (A 1)a in Appendix C.I (also suffers from performance drop).

---

(CC), one agent must send a private message to the other over a public channel with a private key, while an adversary tries reconstruct the message without the key. In the above tasks, we consider a fully cooperative setting where the adversaries are pre-trained by MADDPG [8] for 10 episodes.
We compare RES against state-of-the-art value factorization algorithms including VDN [33. QMIX
1291. QTRAN (31), Weighted QMIX (including CW-QMIX and OW-QMIX) [27]. and QPLEX (38
using the PyMARL (0) implementations and setup, and the popular actor-critic algorithm MADDPG 18 For RES- REIX, we fix the inverse temperature 3 to be 0.05 while the regularization coefficient
is selected based on a grid search over (le 2, 5e 2, le 1, 5e - 1} as investigated in Section
5.1.3
Each algorithm is run with five random seeds, and is reported in mean + standard deviation. A
detailed description of the tasks and implementation details is in Appendix E.1.
5.1.1 Performance Comparison
We first investigate how much of a performance improvement RES-QMIX achieves over QMIX. Performance comparison in different environments is shown in Figure 5| and the mean normalized return averaged over different environments can be found in Appendix E.2. The results show that RES- QMIX significantly outperforms QMIX in performance and efficiency, and achieves stable learning behavior, without any catastrophic performance degradation. We then investigate the performance of RES-QMIL in comparison with state-of-the-art baselines. As shown in Figure 5 RES-QME RES-QMIX significantly outperforms all baselines and achieves tfate-o--the-ar performance in PP, PD, and W tasks. In the CC environment, RES-QM RES-QMIX matches the best performers including VDN, QTRAN and QPLEX, while QMIX and Weighted QMIX suffer from oscillation. We also demonstrate the robust performance of RES-QMIX in stochastic environments in Appendix E.3.
QMIX
VDN
QTRAN
CW-QMIX
OW-QMIX
300
53
40
40
35
10
0.
20
25-
10
20
-10
0
100
100
(K109)
Sphoode (x107)
Spooz (x109)
Splocce 1x100 (4109)
(a) Predator-prey.
(b) Physical deception.
(c) World.
(d) Covert communication.
Figure 5: Performance comparison.
5.1.2 Value Estimation Analysis
To understand the reasons for RES-QMIX'S better performance, we analyze the bias of value estimation (the difference between estimated values and corresponding true values, which are com- puted in the same way as in Section 4) in predator-pree prey. To facilitate a fair comparison among different categories of al- gorithms including value-based and actor-critic methods, we normalize the bias of each method by 100 estimated value true value Itree value] Figure 6 shows that both QMIX and Weighted QMIX suffer from large and rapidly increasing overestimation bias, yielding the severe performance degradation shown in 5 a). Value estimates of VDN, which based on a linear decomposition of Qtot. increase more slowly at the end of training. However, it still incurs large overestimation as in QTRAN and QPLEX. Unlike all other value factorization methods, MADDPG learns an unfactored critic that directly conditions on the full state and joint action. It is less sample efficient, which indicates that value factorization is important in these tasks [14 13) Thus, MADDPG results in a lower return and value estimates (shown in Appendix E.4) compared to all other value factorization methods, but still overestimates. RES-QMIX achieves the smallest bias and fully mitigates the overestimation bias of QMIX, resulting in stable performance and outperforming all other methods.
NE5-OMX
MADEPG
GME
CM (2-4
(IN OMX
GFLEX
15
Figure 6: Normalized bias of value estimates.
7

---

5.1.3 Ablation Study
We now analyze how sensitive RES- RES-QMIX is to some important hyperparameters, and the effect of each component in our method including the regularizer, the softmax operator, and the approximation scheme in the predator-prey task. Full results for all environments be found in Appendix E.5.
The effect of the regularization coefficient A. Figure a) shows the performance RES-QMIX with varying A. RES-QMIX is sensitive to this hyperparameter, which serves critical role in trading off stability and efficiency. A small value of X fails to avoid the performance degradation, while a large value of À focuses more on learning based on the regularization term instead of the bootstrapping target, and affects learning efficiency. There exists an intermediate value that provides the best trade-off. In fact, we find that this is the only parameter that needs to be tuned for RES EES-.
The effect of the inverse temperature 3. shown in Figure (b), RES- QMIX is insensitive to the hyperparameter B, where the performance remains competitive for wide range of B. This is different from previous studies [32 26 25] that are usually sensitive to the inverse temperature parameter, since they solely relies on the softmax operator for overestimation reduction (which is insufficient in the multi-agent setting as discussed in Section 3). We fix 3 in DES-QMIX to be 0.05 due to the relatively low sensitivity with respect to B, which performs the best, in all multi-agent particle environments.
The effect of each component. By comparing RES- RES-QMIX against RE-QMIX and S-QMIX in Figure(Jc). we see that the regularization component is critical for stability, while combining with our softmax operator further improves learning efficiency.
The effect of the approximation scheme. We compare proposed approximation scheme for the softmax operator with a random sampling scheme and a direct computation the joint action space. Specifically, RES-QMIX (RS) randomly samples the same number of joint actions in RES- QMIX, while RES-QMIX (DC) directly computes softmax in the joint action space. The runtime for QMIX, RES-QMIX, and RES-QMIN (DC) is 4.8, 5.2, and 10.7 hours respectively, which shows that RES-QMIX only requires a small amount of extra computation compared to QMIX, and is much more computationally efficient than RES- -MSII (DC). Additionally, from Figure (c), outperforms RES-QMIX (DC), showing that our approximation scheme is not only a necessary compromise for computational efficiency, but also improves performance as discussed in Section RES- RES-QMIX also significantly outperforms its counterpart with random sampling, which also validates its effectiveness.
OPPC 28-31
(ES-NK 1032
181 18-1 1850
K25 0PPC (1
1E544K11-11 15)
09.0
65
(a)
(b)
(c)
(a)
(b)
Figure 7: Ablation study. (a) Varying A. (b) Varying 3. (c) The effect of each component (the regularizer, the softmax operator, and the approximation scheme).
Figure Mean normalized re- turn of RES when applied to (a) Weighted QMIX and (b) QPLEX.
5.1.4 Applicability to Other Algorithms
The proposed RES method general and can be readily applied to other Q-learning based MARL algorithms. To demonstrate its versatility, we apply it to two recent algorithms, Weighted QMIX 27 and QPLEX [8). For Weighted QMIX, we use OW-QMIX as the base algorithm because outperforms CW-QMIX as shown in Figure 5 The improvement in mean normalized return of RES- based methods over their vanilla counterparts while the full comparison of learning curves in each environment is in Appendix E.6. As demonstrated, RES- ReiihWegt QMIX and RES-QP RES-Q provide consistent improvement performance and stability over Weighted QMIX and QPLEX, respectively, demonstrating the versatility of our RES method.
different environments is summarized in Figure 8

---

5.2 StarCraft II Micromanagement Benchmark
To demonstrate the ability of our method to scale to complex scenarios, also evaluate it on the challenging StarCraft II micromanagement tasks [30] by comparing RES-QMIX to QMIX using SC2 version 4.10 for five random seeds. Both algorithms
implemented using the PyMARL framework [30] with default hyperparameters as detailed in Appendix E.I, We evaluate the method maps with different difficulties ranging from easy (2s3z, 3s52), hard (2c_vs, 64zg), to super hard (MMM2) as classified in (30), with a detailed description in Appendix E.1.2.
Figures P (d) show the test win rate. RES- RES-QMIX provides consistent performance improvement over QMIX. Additional comparison results with the most competitive baseline QPLEX, as in the multi-agent particle tasks, provided in Appendix E.8, where RES QMIX also outperforms QPLEX. Additionally, we show that RES is still effective even without double estimators. The results are presented in Appendix E.9, showing that RES-QMIS (single) outperforms both QMIX and QMIX (single) on all maps we tested.
544
6.2
52-
0.00
600 625
125 LX L75
M lerange
M: leunge
48 10
(a) 2s3z.
(b) 3s5z.
(c) 2c_ 64zg.
(d) MMM2.
Figure 9: Comparison of RES-QMIX and QMIX in StarCraft II micromanagement tasks.
6 Related Work
Centralized training with decentralized execution (CTDE) 23 15 where large number of recent work focuses on training agents under this paradigm. MADDPG [ is an off-poligg actor-critic algorithm that extends DDPG I7 to the multi-agent setting. Another line of research focuses on value-based Q-learning algorithm, which learns a centralized but factored joint action-value function Qtot- For instance, VDN factorizes the joint-action Q-function into linear combination of agent-wise utilities, and QMIX (29) improves the representation capability using non-linear monotonic mixing network. There has also been a number of approaches improving QMIX's representation capability including QTRAN [1. Weighted QMIX (27 QPLEX 38 and
is popular paradigm in MARL,
its exploration ability [19 10].
Methods to alleviate overestimation have been extensively studied in reinforcement learning, with a focus on the single-agent case [ 37 32
16
5
8 25 However, as shown in (36), there is
I1 37 uses a pair of independent is shown that the softmax operator effective for reducing estimation bias in the agentt setting. However, compute the softmax operator in the multi-agent case due to the exponentially-sine space, for which we propose an efficient approximation scheme. Ackermann al. 1 extend TD3 [ to the multi-agent setting while Gan et al. [9] propose a soft Mellowmax operator [ to tackle overestimation in MARL. However, the analysis in 9 is based on the assumption that the gradients 0f. are bounded, which might not hold in practice as we have shown in Figure (more technical discussion is Appendix F). Both methods fail to tackle the severe overestimation problem as shown in Figure 2 and Appendix E.7.
no unbiased estimator general settings. Double leamnnng
estimators to reduce overestimation in Q-learning. In 32 26
challenging to joint action
To improve learning efficiency, He et al. [2 propose learning objective based on lower and upper bounds of the optimal Q Q-function. As the upper bound is based on N-step returns, it cannot avoid the severe overestimation as investigated in Section 4 Self-imitation learning (SIL) [2T] aims to improve exploration via leveraging the agent's 's past good experiences, which only performs SIL updates when the estimated value function is smaller than the discounted return. However, this is not effective for reducing overestimation bias in case, as the SIL part pays little attention to experiences whose

---

estimated values are greater than the discounted return is related the mixed Monte Carlo update 3 24 severe overestimation opposed to speed up learning.
The update rule of RES shown in Theorem However, our primary motivation reduce
7 Conclusion
Overestimation is a critical problem in RI., and has been extensively studied in the single-agent setting. In this paper, we showed that it presents more severe practical challenge in MARL than previously acknowledged, and solutions in the single-agent domain fail to successfully tackle this problem. We proposed the RES method based on a novel regularization-bast based update and the softmax operator with an efficient and reliable approximation in novel way. Extensive experiments showed that RES- QMIX significantly reduces overestimation and outperforms of-eeoof-hhe-at baselines. RES is general and can be applied to other deep multi-agent Q-learning methods, and can also scale to a set of challenging StarCraft micromanagemeett tasks. The analysis and development of RES shed light how to design better value estimation in MARL. Interesting directions for future work include theoretical study for the phenomenon discovered Section 3] an adaptive scheduling for the regularization coefficient (e.g., meta- meta-gradient approaches [40]), and the application of RES to other MARL methods.
Acknowledgments and Disclosure of Funding
The work of Ling Pan and Longbo Huang is supported in part by the Technology and Innovation Major Project of the Ministry of Science and Technology of China under Grant 2020AAA0108400 and 2020AAA0108403. Ling Pan is supported by Microsoft Research Asia Fellowship. Tabish Rashid is supported by an EPSRC grant (EP/M508 1/1, EP/N509711/1) This project has received funding from the European Research Council (ERC), under European Union's Horizon 2020 research and innovation programme (grant agreement number 637713). We thank Qingpeng Cai and Tarun Gupta for insightful discussion.
References
[1] Ackermann, Gabler, T. Osa, and M. Sugiyama. Reducing overestimation bias in multi-agent domains using double centralized critics. arXiv preprint
2019.
[2] O. Anschel, N. Baram, and N. Shimkin. Averaged-dqn: Variance reduction and stabilization for deep reinforcement learning. In International Conference on Machine Learning, pages 176-185. PMLR, 2017.
[3] M. Bellemare, S. Srinivasan, G. Ostrovski, T. Schaul, D. Saxton, and R. Munos. Unifying count-based exploration and intrinsic motivation. In Advances in Neural Information Processing Systems, volume 29, pages 1471-1479, 2016.
[4] Y. Cao, W. Yu, W. Ren, and G. Chen. An overview of recent progress in the study of distributed multi-agent coordination. IEEE Transactions on Industrial informaties, 9()):227-433 2012.
[5] J. D. Co-Reyes, Y. Miao, D. Peng, Q. V. Le, S. Levine, H. Lee, and A. Faust. Evolving reinforcement learning algorithms. In International Conference on Learning Representations, 2021.
[6] C. S. de Witt, B. Peng, P.-A. Kamienny, P. Torr, W. Böhmer, and S. Whiteson. Deep multi- agent reinforcement learning for decentralized continuous cooperative control. arXiv preprint arXiv:2003.06709, 2020.
[7] J. Foerster, G. Farquhar, T. Afouras, N. Nardelli, and S. Whiteson. Counterfactual multi-agent policy gradients. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
[8] S. Fujimoto, H. Hoof, and D. Meger. Addressing function approximation error in actor-critic methods. International Conference on Machine Learning, pages 1587-1596, 2018.
In Appendix A.3, we also compare RE-QM RE-QMIX with variant that only activates the penalty when the estimated Q Q-value larger than the discounted return; its value estimates are close those of RE-QMIX
10

---

[9] Y. Gan, Z. Zhang, and X. Tan. Stabilizing learning via soft mellowmax operator. arXiv preprint arXiv:2012.09455 2020.
[10] Gupta, A. Mahajan, B. Peng, W. Böhmer, and Whiteson. Uneven: Universal value exploration for multi-agent reinforcement learning. arXiv preprint arXiv:2010.02974, 2020.
[11] H. Hasselt. Double q-learning. In Advances in Neural Information Processing Systems, volume 23, pages 2613-2621, 2010.
[12] S. He, Y. Liu, A. G. Schwing, and J. Peng. Learning to play in a day: Faster deep reinforcement learning by optimality tightening. In International Conference on Learning Representations, 2016.
[13] S. lqbal, C. A. S. de Witt, B. Peng, W. Böhmer, S. Whiteson, and F. Sha. Ai-qmix: Attention and imagination for dynamic multi-agent reinforcement learning. arXiv preprint wiXv:2006.04222. 2020.
[14] S. Iqbal and F. Sha. Actor-attention-eriiie for multi-agent reinforcement learning. In Interna- tional Conference on Machine Learning, pages 2961-2970. PMLR, 2019.
[15] L. Kraemer and B. Banerjee. Multi-agent reinforcement learning as rehearsal for decentralized planning, Neurocompuling, 190:82-94, 2016.
[16] Q. Lan, Y. Pan, A. Fyshe, and M. White. Maxmin q-learning: Controlling the estimation bias of q-learning. In International Conference on Learning Representations, 2020.
[17] T. P. Lillierap, J. J. Hunt, A. Pritzel, N. Heess, T. Erez, Y. Tassa, D. Silver, and D. Wierstra. Continuous control with deep reinforcement learning. arXiv preprint arXiv:1509.02971, 2015.
[18] R. Lowe. Y. I. Wu, A. Tamar, J. Harb, O. P. Abbeel, and I. Mordatch. Multi-agent actor-critic for mixed cooperative-compeiiii environments. In Advances in neural information processing systems, pages 6379-63999 2017.
[19] A. Mahajan, T. Rashid, M. Samvelyan, and S. Whiteson. Maven: Multi-agent variational exploration. In Advances in Neural Information Processing Systems, volume 32, 2019.
[20] L. Matignon, L. Jeanpierre, and A.-I. Mouaddib. Coordinated multi-robot exploration under communication constraints using decentralized markov decision processes. In AAAI 2012, pages p2017-2023, 2012.
[21] J. Oh, Y. Guo, S. Singh, and H. Lee. Self-imitation learning. In International Conference on Machine Learning, pages 3878-3887. PMLR, 2018
[22] F. A. Oliehoek, C. Amato, al. A concise introduction to decentralized POMDPs, volume 1. Springer, 2016.
[23] A. Olichoek, M. T. Spaan, and N. Vlassis. Optimal and approximate q-value functions for decentralized pomdps. Journal of Artificial Intelligence Research, 32:289-353. 2008
[24] G. Ostrovski, M. G. Bellemare, A. Oord, and R. Munos. Count-based exploration with neural density models. In International conference on machine learning, pages 2721-2730. PMLR, 2017.
[25] I.. Pan, Q. Cai, and L. Huang. Softmax deep double deterministic policy gradients. In Advances in Neural Information Processing Systems, volume 33, pages 11767-11777, 2020.
[26] L. Pan, Q Cai, Q Meng, W. Chen, and L. Huang. Reinforcement learning with dynamic boltzmann softmax updates. In Proceedings of the Twent-Ninth International Joint Conference on Artificial Intelligence, pages 1992-1998, 2020.
[27] T. Rashid, G. Farquhar, B. Peng, and S. Whiteson. Weighted qmix: Expanding monotonic value function factorisation for deep multi-agent reinforcement learning. Advances in Neural Information Processing Systems, volume 33, pages 10199-102100 10210, 2020.
[28] T. Rashid, M. Samvelyan, C. S. De Witt, G. Farquhar, J. Foerster, and S. Whiteson. Monotonic value function factorisation for deep multi-agent reinforeement learning. Journal of Machine Learning Research, 21(178):1-51, 2020.
[29] T. Rashid, M. Samvelyan, C. Schroeder, G. Farquhar, J. Foerster, and S. Whiteson. Qmix: Mono- tonic value function factorisation for deep multi-agent reinforcement learning. International Conference Machine Learning, pages 4295-4304, 2018.

---

[30] M. Samvelyan, T. Rashid, C. S. de Witt. G. Farquhar, N. Nardelli, T. G. Rudner, C.-M. Hung, H. Torr, J. Foerster, and S. Whiteson. The starcraft multi- agent challenge. arXiv preprint arXiv: 210..99024400 04043, 2019.
[31] K. Son, D. Kim, W. J. Kang, D. E. Hostallero, and Y. Yi. Qtran: Learning to factorize with transformation for cooperative multi-agent reinforcement learning. In International Conference on Machine Learning, pages 5887-5896, 2019.
[32] Z. Song, R. Parr, and L.. Carin. Revisiting the softmax bellman operator: New benefits and new perspective. In International Conference on Machine Learning, pages 5916-5925. PMLR, 2019.
[33] Sunchag, G. Lever, A. Gruslys, W. M. Czarnecki, V. F. Zambaldi, M. Jaderberg, M. Lanctot, N. Sonnerat, J. Z. Leibo, K. Tuyls, et al. Value-decoomposttonn networks for cooperative multi-agent learning based on team reward. In AAMAS, pages 2085-2087, 2018.
[34] S. Thrun and Schwartz. Issues in using function approximation for reinforcement learning. In Proceedings of the Fourth Connectionist Models Summer School, pages 255-263. Hillsdale, NJ, 1993.
[35] N. Tsitsiklis and B. Van Roy. An analysis of temporal-difference learning with function approximation. IEEE transactions on automatic control, 42(5):674-690, 1997.
[36] H. Van Hasselt. Estimating the maximum expected value: an analysis of (nested) cross validation and the maximum sample average. arXiv preprint 1.02. 2013.
[37] H. Van Hasselt, A. Guez, and D. Silver. Deep reinforcement learning with double q-learning. In Proceedings of the AAAI conference on artificial intelligence, volume 30, 2016.
[38] Wang, Z. Ren, T. Liu, Y. Yu, and Zhang. Qplex: Duplex dueling multi-agent q- q-learning. In International Conference on Learning Representations, 2021.
[39] C. J. Watkins and P. Dayan. Q-learning. Machine learning, 8(3-4):27--29,, 1992.
[40] Z. Xu, H. P. van Hasselt, and D. Silver. Meta-gradient reinforcement learning. Advances in Neural Information Processing Systems, 31:2396- 2407, 2018.
[41] Y. Yang. J. Hao, B. Liao, K. Shao, G. Chen, W. Liu, and H. Tang. Qatten: A general framework for cooperative multiagent reinforcement learning. arXiv preprint (1XXi:20002.03939,, 2020.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [Yes] The discussion is in Appendix G.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] The complete proofs for Theorems 2 and are in Appendix B.1, C, D respectively.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as a URL)? [Yes] We implement method and compare with baselines using open sourced PyMARL framework. The code is publicly available at wthhtts:: //gtttb.tubu.. com/ ingiiingn....
(b) Did you specify all the training details (e.g.. data splits, hyperparameters, how they were chosen)? [Yes] See Section 5.1 Section 5.2 and Appendix E.1
(c) Did you report error bars (e-g., with respect the random seed after running experi- ments multiple times)? [Yes] Results are reported in mean + std.
12

---

(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
4. If you using existing assets (e.g., code, data, models) curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any new assets either in the supplemental material as a URL? [N/A]
Our experiments are conducted based on open-sourced multi-agent particle framework and StarCraft micromanagement tasks.
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [Yes]
(e) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [N/A] Our experiments are conducted based on open- sourced multi-agent partiele framework and StarCraft II micromanagement tasks.
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "zDUfnMRCGkT", "reviewer": "Reviewer_FuxW", "summary": "Overestimation in Q-learning is an important problem. However, there has been less attention on the overestimation problem in multi-agent setting compared to the single-agent setting. The authors show that Q-learning in multi-agent setting suffers from overestimation even more than the previously acknowledged. This paper proposes a regularized update scheme that tackles this issue. Also, the new softmax operator, Regularized Softmax (RES) is introduced. Empirical results on various domains, including Starcraft II tasks, are given to support the claim. ", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "- The introduction part was very well written. Overestimation is a big challenge in Q-learning, and has been investigated very much by RL community; however, overestimation in multi-agent setting has been less investigated. The authors show that the traditional approaches tackling overestimation in single-agent setting, such as double estimator, resolve the overestimation in multi-agent settings, hence the need for another approach for tackling overestimation in multi-agent settings. \n- Background (Dec-POMDP, Deep multi-agent Q-learning, CTDE) was very helpful for readers. \n- The argument made in the introduction is extended in the section 3, where the authors did experiments on tackling overestimation using clipped double q-learning and gradient regularization (and the combination of both), and still show that these approaches are not sufficient. Good flow of logic. \n- Next approach was to introduce a baseline into the penalty --> \\lambda (Q_tot(s,u) - b(s,u))^2. \\lambda is a regularization coefficient. N-step return or discounted return can be a baseline. \n- The next approach to further resolve overestimation bias caused by max operator was to introduce another softmax operator for multi-agent setting. This softmax operator contains inverse temperature parametere \\beta just like a boltzmann softmax. Depending on the choice of \\beta, the operator either converges to the max or the mean. \n- I think these two step approaches (baseline and softmax) were quite original and novel. \n- I've checked most of the proofs, and couldn't find any flaws. \n- Multiple Experiments were given in the section 5. \n- Authors provided the analysis on the effect of parameters, including regularization coefficient \\lambda and \\beta. It is quite surprising that the hyperparameter sensitivity of \\beta is quite low. \n\nQuestions\n\nQ1. The authors mentioned that RES_QMIX is insensitive to the inverse temperature parameter \\beta, and set \\beta=0.05. Could you give me a more intuition on how this happens? (Usually, the hyperparameter sensitivity and the choice of the optimal parameter is a big issue in softmax operators). Are there any experiments other than the one given in the Figure 7 single domain?\n\nQ2. Seems that the performance of RES-QMIX is quite sensitive to the choice of regularization coefficient labmda. Can you think of any adaptive or automated method to tune the parameter without exhaustive grid-search? Have you ever considered a method to schedule the parameter lambda along the training? or learn to learn the parameter as in the meta-gradient RL (Xu, van Hasselt, Silver et al)? \n\n\nSuggestions for references:\n\nI'd like the authors add the following citation on the multi-agent RL and overestimation in the related work:\n\n[1] Fu,  Z.,  Zhao,  Q.,  and Zhang,  W.  Reducing overestimation in value mixing for cooperative deep multi-agent reinforcement learning. ICAART, 2020.\n\nAlso, the following works that handle overestimation bias in Q-learning (more recent works): \n\n[2] R.Zhu, M. Rigotti. Self-correcting Q-learning. AAAI 2021. \n\n[3] S. Kim, K. Asadi, M. Littman, G. Konidaris. DeepMellow: Removing the Need for a Target Network in Deep Q-learning. IJCAI 2019. \n\n[4] Z. Zhang, Z. Pan, M.J. Kochenderfer. Weighted Double Q-learning. IJCAI 2017", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I don't see any potential negative societal impact of this work. ", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "9 "}, "extra_text": {}}, {"review_id": "myLLfRfEHv6", "reviewer": "Reviewer_9Gqb", "summary": "The paper addresses overestimation in return estimator in the context of multi-agent reinforcement learning, while claiming the overestimation could be more severe in multi-agent than in single-agent setting. The authors propose an update scheme to penalize large joint-action Q values that deviate from a baseline through the use of regularizer term in the Bellman update; and include an approximated softmax operator to further improve the overestimation issue. The approximated softmax operator is introduced to reduce computational complexity of employing softmax in multi-agent scenario. ", "questions": "", "limitations": "", "rating": 7, "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": "Originality: The authors made clear the difference of its method of applying their proposed approximate softmax operator on Q_tot instead of applying softmax on agent-wise utilities, with the later result available in Appendix. This originality is supported with clear reasoning and theoretical claim of convergence for this approximated softmax operator. The authors also demonstrated the difference of their adopted baseline in the regularizer term from typical implementation of advantage function and made clear to deliberately avoid the presence of Q_tot; instead, the direct discounted return is used.\nQuality: The paper establishes the claim of overestimation in QMIX through empirical support in a predator-prey task, in which the value estimators observed to grow without bounds, exploding gradient and weights, causing it to suffer catastrophic performance drop. The authors also provided theoretical formulation to proof reduced trajectory bias using their proposed RES loss function. The authors also examined the proposed method’s sensitivity to hyperparameters and showed better stability. The authors also showed slightly increased runtime of their method compared to QMIX.\nClarity: Paper is well-organized with detailed information of applying the two core components in their proposal: 1) regularizer term and 2) approximated softmax, with the effect of each individual approach is carefully examined. Theoretical justification of reduced bias is also provided for added confidence.\nSignificance: The authors demonstrated the presence of overestimation bias in MARL (which may be overlooked by many) and achieve significant performance improvement over other MARL methods. They also showed the versatility of their algorithm to be applied to other MARL algorithms other than QMIX. An added value is that the paper is written with a clear thought process of tackling the issue and step-by-step reasoning to apply the two core components could serve a good reference for similar research approaching such issue. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The potential societal impact is discussed in Appendix. However, the authors seem to misinterpret the motive of this section and provided a positive (instead of negative) societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "hoiBrOWprl", "reviewer": "Reviewer_QGZD", "summary": "The author proposes a solution to overestimation in MARL, which is called RES deep Q-learning. The author penalizes large joint-action Q values by two approaches: a regularizer towards discounted return, and an estimated softmax operator. The author also constructs an action subspace for efficient softmax approaximation.", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Generally, I don’t feel very excited after a thorough understanding of this paper. The two main works of the model, mentioned in Summary, are similar to previous methods. For example, the GradReg is a regularization-based method, and softmax operator has been widely study in single-agent RL settings. Though sufficient experimental results are presented, the overall paper is not convincing due to the following problems:\n(1)\tThere’s no significant novelty in this paper. The author just transfers existing solutions in traditional RL to MARL, adding some tricks for efficient computation.\n(2)\tQMIX suffers from severe overestimation, because the model performance decreases rapidly in four environments after millions of episodes. However, it seems that the overestimation disappears in StarCraft II micromanagement tasks, as the win rate increases without significant degradation (in Figure. 9). Is overestimation a problem with all MARL models in all environments? What is the significance of studying the overestimation problem of specific MARL algorithm in specific environments?\n(3)\tMore theoretical analysis is needed, and experimental results are not quite intuitive. Why those solutions to overestimation in single RL settings fail in MARL? It’s difficult to have an intuitive inspiration without any theoretical analysis. It is also confusing that an experimental result (Figure 1) is given in Introduction without any description in details.\n(4)\tHow is the RES method applied to other algorithms, e.g. weighted QMIX and QPLEX? More details for description is needed.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The limitation can be referred to “Main Review” and there is nearly no potential negative societal impact of this work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "15"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper addresses an important well-known problem (Q-value overestimation), but in a more context which is more complex than the traditional setup (Multi-Agent RL). In this context the authors claim that the problem is less studied, which the reviewers generally don't contest (and I personally agree as well). This paper studies this problem in this context a clear way, and also propose an algorithm to mitigate it.

Two of the reviewers are voting to accept the paper, whereas the third is recommending a reject. I still recommend acceptance, because that's the majority vote but also because I am not convinced that the third reviewer (QGZD) has a full understanding of the paper. The authors have addressed the criticisms of QGZD and I tend to agree with them. Unfortunately QGZD hasn't answered the rebuttal.
Decision: Accept (Poster)