UTS: When Monotonic Value Factorisation Meets Non-monotonic and Stochastic Targets
Authors: Zeyang Liu
Lipeng Wan
Xue Sui
Xingyu Chen
Xuguang Lan
Venue: Submitted to ICLR 2023 (2023)
Keywords: Value Decomposition
Multi-Agent Reinforcement Learning

Abstract: Extracting decentralised policies from joint action-values is an attractive way to exploit centralised learning. It is possible to apply monotonic value factorisation to guarantee consistency between the centralised and decentralised policies. However, the best strategy for training decentralised policies when the target joint action-values are non-monotonic and stochastic is still unclear. We propose a novel value factorisation method named uncertainty-based target shaping (UTS) to solve this problem. UTS employs networks that estimate the reward and the following state's embedding, where the large prediction error indicates that the target is stochastic. By replacing deterministic targets for the suboptimal with the best per-agent values, we enforce that all shaped targets become a subset of the space that can be represented by monotonic value factorisation. Empirical results show that UTS outperforms state-of-the-art baselines on multiple benchmarks, including matrix games, predator-prey, and challenging tasks in the StarCraft II micromanagement.

Under review as a conference paper at ICLR 2023
UTS: WHEN MONOTONIC VALUE FACTORISATION MEETS NON-MONOTONIC AND STOCHASTIC TARGETS
Anonymous authors Paper under double-blind review
ABSTRACT
In the paradigm of centralised training with decentralised execution, monotonic value decomposition one of the most popular methods guarantee consistency between centralised and decentralised policies. This method always underestimates the value of the optimal joint action and converges to the suboptimal because it can only represent values in the restricted monotonic space. A possible way rectify this issue is to introduce a weighting function to prioritise the real optimal joint action and learn biased joint action-value functions. However, there may not exist an appropriate weight to solve more general tasks with non-monotonic and stochastic target joint action-values. To solve this problem, we propose a novel value factorisation method named uncertainty-basse target shaping (UTS), which projects the original target to the space that monotonic value factorisation can represent based on its stochasticity. First, we employ networks to predict the reward and the embedding of the next state, where the prediction error quantifies the stochasticity. Then, we introduce target shaping function to replace the targets for deterministic suboptimal with the best per-agent value. Since we remain the optimal policy unchanged during shaping, monotonic value decomposition can converge to the real optimal with any original targets. Theoretical and empirical results demonstrate the improved performance of UTS in the task with non-monotonn and stochastic target action-value functions.
INTRODUCTION
Recent progress in cooperative multi-agent reinforcement learning (MARL) has shown attractive prospects for various real-world applications. such as the smart grid management (Aladdin et al.) 2020) and autonomous vehicles (Zhou et al. (02II. Due to practical communication constraints and intractably large joint action space, decentralised policies are often used in MARL. It is pos- sible to use extra information from the environment and other agents in a simulated or laboratory setting. Exploiting this information can significantly benefit policy optimisation and improve learning performance (Foerster et al., 2016 2018: Rashid et al., (2020).
In the paradigm of centralised training with decentralised execution (CTDE), agents' policies trained with access to global information in a centralised way and executed only based on local histories in a decentralised way (Olichock et al.] 20088) Kraemer & Banerjee (016). One of the most significant challenges is to guarantee the consistency between the individual policies and the centralised policy, i.e., the Individual-Global Max (IGM) principle (Son al. 2019). In value decomposition methods. QMIX (Rashid et al. 2018) applies a monotonic mixing network to factorise the joint Q-value function, which naturally meets the IGM principle. Inspired by QMIX, many algorithms are proposed to improve coordination from different perspectives, e.g., multi-agent exploration (Mahajan et al. 2019),, role-based learning (Wang et al., 2020b/c), c). and policy-based algorithms (Wang et al.) 2020d). However, they represent the same class of joint Q-values as QMIX because they use the same monotonic mixing network.
However, since QMIX can only represent values in the restricted monotonic space, there exists a gap between the approximated joint Q-values and the non non-monotonic target values Q from the environment. In some special tasks, QMIX can underestimate the value of the real optimal joint action and converge to a suboptimal (Son et al., 2019: Mahajan et al. 20199) Rashid et al. 2020). Recent works try solve this representational limitation from two different perspectives. This first category

---

Under review as a conference paper at ICLR 2023
introduces the joint actions (Wang et al.) 2020a Mahajan et al. 2021) or pairwise interactions (Böhmer et al. 2020; Li et al. 2021) into centralised learning to achieve full representational capacity for target Q-values. However, learning such centralised values is difficult due to the large joint action space. Another category is to prioritise the real optimal joint action and learn biased joint Q-value functions. WQMIX (Rashid et al. (020) introduces weighting function into the projection from the larget value functions to the joint Q-values and uses it to down-weight every suboptimal action whose target value less than the current estimate. However, the poor empirical results on decentralised micromanagement tasks in StarCraft II show that it is difficult to apply the weighting function to more general tasks (Rashid et al. 2020 Wang et al., 2020a). We prove that the weight for the suboptimal should be small to help QMIX focus on the representation of the optimal joint Q-value and solves the non-monotonic targets. addition, the weight for each action should be uniform to avoid overestimating the suboptimal whose target is large with low probability. Due to this contradiction, there may not exist an appropriate weight to recover the optimal policy when the target is non- mon-monotonic and stochastic.
This paper aims to take a step towards the latter category. We propose a novel value factorisation method named uncertainty-batt based target shaping (UTS), which projects the original target to the space that monotonic value factorisation can represent based on its stochasticity. First, we formulate two prediction problems and use the prediction error quantify the stochasticity of the target joint Q-values. We employ a reward predictor and a state predictor to approximate the standard deviation of the reward and the embedding of the following state. The predicted standard deviation of the reward and the error of the state are expected to be significant if the pair leads to stochastic reward and stochastic state transition, respectively. Then, we introduce a shaping function to project the original targets Q to the monotonic space and keep the optimal policy unchanged. In practice, the best action value network is applied to predict the action value when each agent gets the cooperation of others. We use the minimal best per-agent values over all agents to replace the suboptimal target. We prove that this shaping can guarantee that all shaped targets are tractable for monotonic value decomposition. In addition, the optimal policy is the same for the original and the shaped targets. Therefore, QMIX can achieve full representational capacity for the shaped target Q-values rather than the original ones and converge to the real optimal.
We list our main contributions as follows:
We first analyse the limitations of the weighting function in value decomposition methods and show that it cannot guarantee convergence to the optimal when target Q-value functions are non- monooontooic and stochastic.
We introduce target shaping function to project the original targets to a monotonic space, which ensures that QMIX can converge to the optimal with any original targets.
We propose uncertainty-base target shaping and empirically show its improved performance in practice, especially in tasks with non-monotonic and stochastic targets.
2 BACKGROUND
A fully cooperative multi-agent task in the partially observable setting can be formulated Decentralised Partially Observable Markov Decision Process (Dec-POMDP) (Oliehoek & Amato 2016), consisting of tuple G = (A, S, 22 O,U, P. R, n, 7), where A I.....n] describes the set of agents, S denotes the set of states, Ω denotes the set of joint observations, and R denotes the set of rewards. At each time step, an agent obtains its observation E 9 based on the observation function O (s, a) S x A - Ω and an action observvttoo history Ta E T = (S2 x U)". Each agent chooses an action ug E U by a stochastic policy Na (ullTa) T U -> [0, 1). forming a joint action U. which leads to a transition on the environment through the transition function P(s', rls, u)
S x x S x R + [0, 1). where r E R is the team reward. The goal of the task to find the joint policy which can maximise the joint Q-vauue function Q" QT((s, u,) E Met [G ( u),
where G = Σ y /rrtt is the discounted return.
VDN (Sunehag et al. 2018). QMIX (Rashid et al. 2018), and WQMIX Rashid et al. 2020) are Q-learning algorithms for the fully cooperative agent tasks, which estimate the joint Q Valuue function Q(s, u) as Qiot with specific forms. Considering only a obsly- setting for case of representation. VDN factorises Qtot into sum of individual Q-value functions. By contrast,
2

---

Under review as a conference paper at ICLR 2023
QMIX applies state-dependent monotonic mixing network to combine per-agent Q- value functions with the joint Q-value function. The restricted spaces of all Qtot that linear and monotonic value factorisations represent are:
Q = -trooe Qtrorl
Σ ua), E ER a=1
(1)
Q = (Qroel (t, = fo(Q1 Qn un)), 05= 3 0, (,s, aQ.
(2)
where the monotonic mixing function fa is parametrised as a feedforward network, whose non- negative weights are generated by hypernetworks that take the state as input.
WQMIX views QMIX an operator Homix Q == arg mi.. Qumu: Easu(y(s, Qior u))
which can be separated into two parts: the first computes the Q-learning target y(s, u) == Err
max Qro u')]. and the second projects the target into Quaes, Then, WQMIX introduces the weighting function into the projection to prioritise the optimal joint Q-value:
I@Qix Q :
arg min E
Σ BEU
w(s ()((ss Qtoe u))²
Since it computationally infeasible obtain the optimal joint Q-value, WQMIX proposes Centrally- Weighted QMIX (CW-QMIB and Optimistically- -eighhedd QMIX (OW-QMIX) to place more importance on better joint actions. In practice, the weighting function w S x U (0, 10.1] is:
y(s, u) Q" (2(ss ú") or w ow (s, (s,u)
y(s, u) Qt,e(s. otherwise
w tr (s, u)
otherwise
where ú* arg max, (so u) is the current greedy joint action, (s, ú") is an approximation of the true optimal value function which not constrained to be monotonic.
CASE STUDIES
In this section, we examine the weightings of WQMIX when the Q-learnin targets are non-monotonic and stochastic. Since the non- non-linear mixing network in WQMIX makes many analysis methods inapplicable, we use WVDN to analyse the fundamental limitations of the weighting. The WVDN operator is defined as TwVDNN == arg min Qur Engu wow (s, ()((s, u) Qro((s, u)) where wol (s, u) is the optimistic weighting from (4)
3.1 NON-MONOTONEE TARGETS
QMIX cannot represent joint Q-value functions that are characterised non non-monotonic, Although this representational limitation will not necessarily result in the convergence to the suboptimal, QMIX
fails to recover the optimal policy with some specific non-monotonic targets (Son et al. 2019). To accurately represent the optimal joint Q-value rather than the suboptimal ones, Rashid et al. (2020)
o introduce the weighting function in 44h to down-weight every suboptimal action. However, the choice of weight is crucial to ensure that WQMIX
overcome the limitations of QMIX.
The weight a should be small enough to prioritise estimating the real optimal action value. We start by analysing a matrix game in Figure II, where each joint action receives a team reward. Our study focuses on the greatest value a to converge to the optimal when the policy is initialised to be suboptimal. Suppose the training dataset has a e-greedy distribution. where the greedy action is to recover the optimal
(u², u²). We find that for WVDN should be smaller than 3e(a-o)++F(cb))
(r- (e-3)
joint policy. The proof can be found in Appendix A.2 In Figure Dp, We show that for WQMIX also should be smaller than specific value to overcome the non-monotonic targets. The complete results are provided in Appendix
3.2 STOCHASTIC TARGETS
The stochasticity of the target value functions comes from both rewards and transitions, i.c., P(s', r|s, u) is not deterministic. Traditional Q-learning algorithms solve this problem by calculating
3

---

Under review as a conference paper at ICLR 2023
the weighted sum of possible rewards and values of the next state multiplied by their probabilities, ie., Q(s, u) = E., En(P(s r|s, ujr +)r 7P(s', rls. u) maxy Q(s', J By contrast, the weighting function in WQMIX prioritises actions whose targets greater than the estimated joint Q-value from the current mixing network. This weighting can be seen as a type of distribution shaping, leading to potential risks in policy learning.
The weight a should be large to anchor down the overestimated value for the suboptimal whose target is huge with small probability. Since r(s u) and maxe' Q(s', u') play an equal role in the target value function, we take the matrix game with stochastic rewards as an example. To get a better understanding of the effect of the weight the stochastic environment, we show numerical example in Figure I. where the suboptimal action u² (uî, uτ) receives 12 with probability 0.5 and O with 0.5, where the optimal is u' (ut, u²). Suppose the training dataset is fixed, where the data has 6-greedy distribution and the greedy action is u². Let Quu) denote the true joint Q-value. Since this matrix game only involves one state, we omit the state s in the value function for simplicity.
02
U1
up
uf
u
Alço
E
1.0
0.5
0.25
uf
U2
u
Mf
uF
u
a
b
b
Analysis
3.0
15.0
52.6
6
w/
6
WVDN
10.5
42.2
100.5
u
C
C
DW-QMIX
12.2 43.2
103.2
un
12/0
6
xx3
6
CW-QMIX
11.5
29.6
83.5
6
6
(a) A
non-monotonil game.
(b) Minimal 1/ar.
(c)
stochastic game.
(d) QMIX (er =1).
02
uf
ui
U2
01
uf
u.
U2
u]
U2
734
7.29
6.06
7.33
7.25
7.29
7.67
6.42
7.98
7.98
6.33
w²
7.29
7.23
6.05
163
7.25
7.2
6,28
ug
7.67
10.9
6.62
uz
7.98
7.98
6.33
6.05
6.03
3.92
6.33
6.28
5.45
ug
6.43
6.63
5.73
6.33
5.51
(e) N0JOW-QP
OW-QMMX((==0))
(f)
CD-C-QQI (ar =0.5).
(g) OW-QMIX (x==0.1).
(h)
CW-QMIX (t==0.1).
Figure 1: (a) The payoff matrix for one-step non-monotonic game, where > >> b. (b) The minimal 1/a to recover the optimal policy with different in the non-monotonic game in (a). where 8 --12
6. (c) The payoff matrix for one-step stochastic game. (d-h) The estimated joint Q-values Qtae returned from QMIX and WQMIX. Boldface means the optimal joint action from the payoff matrix or the greedy joint action from the Qtot-
Figure 1h demonstrate the joint Q-values Qtor(1) returned from QMIX and WQMIX with different a. QMIX is special case of WQMIX (a 1) and thus represents the joint Q-value perfectly. By contrast. WQMIX with a small weight is drawn to the suboptimal u² and thus has an incorrect argmax. OW-QMIX returns overestimated Quo)(u))
10.9 Qtoe (u*) and thus converge the suboptimal ù = u² In particular, CW-QMIX places more importance on u² when it is not the greedy action and receives the reward of 12, leading to overestimated value Qtor Quor(u") > Q(u"))
6. With the increase of Qtoe (u"), u² becomes the greedy action once Qtor (u") > Qror (u"). In this situation, CW-QMIX does not place the for u when it receives the reward of O, leading to the decrease of Quor(u"). As a result, CW-QMIX is stuck in this loop and cannot converge to any policy.
Theorem Let NWVDNQ := arg min au EQte/ / EnEr wou(s, (Q(,)) - Qror(s, (tor(s,u)) u))² and wow (s, u) is the optimistic weighting from Then EQ such that arg max NWVDNQ # arg max Q for any 1].
The proof is provided in Appendix A.2 An intuitive understanding is that the weight a in WVDN has an upper bound deal with non-monotonic Q-learning targets and has a lower bound anchor down the overestimated suboptimal value due to undesirable weights in the stochastic environment. The empirical results in Appendix show that WQMIX also suffers from this contradiction and fails to converge to the optimal.
4 METHOD
In this section, we introduce a shaping function to generate the shaped target Q (s. u) to replace the original target Q(s, u). The shaping function has the following properties: 1) policy invariance, which means the optimal policy remains unchanged during shaping, i.c., arg max, Q' u) = arg max, Q(,, u). 2) full representational capacity, i.e., all shaped joint Q-values should belong
4

---

Under review as a conference paper at ICLR 2023
to subset of Qmef, Note that we achieve the full representational capacity w.r. the shaped targets rather than the original ones. QMIX can recover the optimal joint policy with arbitrary original targets based on these properties. To this end, we first predict the standard deviation of the reward and the embedding of the next state. We then split the stochastic joint Q-values from the sampled data according to the prediction error. Next, we employ network that estimates the best action value for each agent. Based on the prediction error and the best action values, we use the shaping function to generate shaped target joint Q-values, which can be represented by monotonic value decomposition.
4.1 UNCERTAINTY ESTIMATION
The stochasticity of the target joint Q-value comes from the stochastic transition of the reward and the state, P(s', s, u). which can be viewed type of the aleatoric uncertainty (Der Kiureghian & Ditlevsen 2009). We propose solution to this undesirable stochasticity using two prediction problems, where the output the standard deviation of the reward and the embedding of the following state of given state-action pair. This involves three neural networks: reward predictor network, state predictor, and a fixed and randomly initialised target network. The reward predictor network takes the state and joint action to the reward f(s, u) S U + R and the uncertainty, i... the standard deviation (s,, u): S x U + R. Based on the Bayesian deep learning method (Kendall & Gal 2017), the reward predictor network is trained by minimising the following loss:
B
1 uj (r' (r' (s, + log "s, us)
where B denotes the batch size of transitions sampled from the replay buffer. The standard deviation is expected to be higher if the state-action pair leads to stochastic rewards.
Inspired by RND (Burda al. 2018), the target network for the second prediction problem takes state to an m-dimensional embedding (($)= : S + R.", where g(s) is a fixed and randomly initialised network. The state predictor fiss, u: 0₂) : x U + I is trained to minimise the prediction error E(s, s') = [[g(s') ) /=s,,,)]² with respect to its parameters 0n. where s' denotes the next state in the sampled trajectory. The prediction error is expected to be higher if the state-action pair results in stochastic transitions. Combining the reward and the state predictors, we define an indicator function where and È are hyper-parameters.
T(s, u)
4.2 SHAPING FUNCTION
QMIX cannot represent the non-monotonic target Q-value because it imposes the monotonic con- straint on the relationship between the joint Q-value and the individual Q-values. Therefore, we can represent the suboptimality of uncooperative actions rather than their exact values. To quantify the sub- optimality of actions, we define the best action value function la Tax ua) = maxy a (s, uay u u_a) as the greatest Q-value of u. when others perform optimally to cooperate with it. qa Tax Ua)) is less than the optimal Q value ua is not part of the real optimal. Inspired by BAIL (Chen et al. 2020). approximate qa (8, Ta: ua) by minimising the following loss:
B a
ΣΣ
K(s, Tex (s, Tas un) - (s, u.))² + A110 1l,
(6)
where B denotes the batch size of transitions sampled from the replay buffer, v/,s,, un) =
(ss, u) + 7 mmax,, (s',, Tha u'a) is the target, À is the regularisation coefficients, K(s, Fay Ua) = for the Q-value whose target is stochastic or smaller than the current estimate, i.e., vā(s, ua) <
(s,s, Ta: Ua) UT(s. u) 1. and K(s, Ta, uo) k > 1 otherwise. Equipped with qu (a Ta: Ua). can compute the original target y(s, T, u) for joint Q-value Qtot and projects it into y (s, T, u). We
define the corresponding shaping function follows:
min (s, Tas Ma)
T( u) = 0 and T)) & Qtoe(s,
(8,T,u)= = aE A
(7)
Tu)
otherwise
where Qia T,; = (7) Qu(Tn: un)) is the joint Q-values parametrized by 0, 0f. > 0, y(S,TTTU r(s, u) max, Qior(s', -', 0') ü arg max, Qroe u), and ø' 8Q.
denotes the parameters of a target network that periodically copied from 0.
5

---

Under review as a conference paper at ICLR 2023
Then, we introduce shaping function f(s, u) project the target Q(s, T, u) into the restricted monotonic space that QMIX can represent. In practice, we replace the target Q(s, T, u) by the minimal value of qa (s, Tax ua) for deterministic and suboptimal joint Q-values. The goal is to ensure that all shaped target value functions at a given state belong to the restricted monotonic space and that the target for the optimal is greater than the suboptimal. We do not change the stochastic targets because QMIX can deal with them already. To improve learning efficiency, we also remain the target unchanged if exceeds the current greedy action value estimate and is deterministic. Qoo T, u, is trained by minimising the following loss:
Σ - (s,
(8)
Monotonic value factorisation with the original target joint Q-values Q induces representational limitation, but it is unclear if the shaped targets do the same. In the following, we give profound understanding of this. We consider only a obsly-observable setting for ease of representation. and our notations do not distinguish the concepts of states and observation-action histories.
Theorem 2 Let Q and Qf be the orignal and the shaped action value based on 77. Then vs E S and Yu U such that arg max, Q(s, U) is unique, arg max, Q' (s,ss) arg max, Q(s, u) and Q' (s, uu E Qmas_
The proof can be found in Appendix A.3 Since all shaped targets Q' (s, u) a given state lie in the restricted monotonic space Q monotonic value factorisation can perfectly represent these values. In addition, the optimal policy remains unchanged during shaping. Therefore, QMIX can now converge to the optimal for any original target Q-value function.
QNIX with orggnal targets
QULX targets
(el Original larget values
(3) Stopod target values
(cl Loes for approxmmating the scget values
(4) Rerward for the curmet groad actionn
25
20
Totsowad
15
in
Olgind
02
U.
200
400
E00
800
1000
200
400
800
000
1000
Inensbote
Dembiion
Figure 2: The performance of QMIX with the original and the shaped target values.
In Figure 2 we compare the performance of QMIX with the original and the shaped target joint Q-values. Consider a 10 x 10 matrix game, where the suboptimal is filled with random numbers generated uniformly between -10 and 9, and the unique optimal value is +10. As shown in Figure b,, the original targets are the rewards from this matrix game, and the shaped targets are obtained based on 7 Figure 2 demonstrates that QMIX can perfectly represent all shaped targets and thus converge to the optimal by showing the loss almost and the test reward is +10 after 400 iterations. By contrast, QMIX with the original targets in Figure 2 keeps fluctuating during training.
RELATED WORK
In this section, we briefly introduce recent related work on cooperative multi-agent reinforcement learning (MARL) in the paradigm of centralised training with decentralised execution (CTDE). One of the most significant challenges in CTDE to ensure the correspondence between the individual Q-value functions and the joint Q-value function Qtot. i.e., the Individual-Global Max (IGM) principle (Son et al. 2019). VDN (Sunehag et al. 2018) and QMIX (Rashid et al. (2118) learn the joint Q-values and factorise them into individual Q-value functions in additive and a monotonic fashion, respectively. Qatten Yang et al., (020bb is a variant of QMIX, which applies a multi-head attention structure to the mixing network. QPD (Yang et al. 2020a) utilises integrated gradients to decompose Qtot along trajectory paths. SMIX(A) (Yao et al., (021) changes the one-step Q-learning target with SARSA()) target for QMIX. RODE (Wang al. 2020c) decomposes joint action

---

Under review as a conference paper at ICLR 2023
spaces into restricted role action spaces to boost learning efficiency and policy generalisation. These methods apply the same monotonic mixing network and thus can only represent the same class as QMIX. However, as many previous studies pointed out, monotonic value factorisation limits the representational capacity of Qtot. and fail to learn the optimal policy when the target Q-value
functions are non-monotonic (Mahajan et al. 2019 Son al. 2019 Rashid et al. 2020
Some recent works try to achieve the full representational capacity of Qiot to solve this problem. QPLEX (Wang et al. (020aa achieves the full representation under the IGM principle theoretically through a duelling mixing network, in which the weights are produced through joint actions. However, it also induces the "vanishing gradient" problem. leading to slow convergence and learning instability, More discussions can be found in Appendix [B.2] Deep coordination graph (Böhmer et al. (020)
decompose the joint state-action value into individual utilities and payoff contributions based on the actions of the agents connected by the (hyper-)edgee Jedges. Tesseract (Mahajan et al., 2021) decomposes the Q-tensor across agents and utilises low-rank tensor approximations to model agent interactions relevant to the task, and thus learns a compact approximation of the target Q-value function. However, since the dimension of the state-action space increases exponentially as the number of agents grows, it is not easy to achieve the full representational capacity in complex MARL tasks.
Another solution is to learn a biased Qeo by prioritising the optimal joint action. QTRAN (on et al. 2019) uses two soft regularisations to align the greedy action selections between the joint Q-value and the individual values. WQMIX (Rashid et al. 2020) introduces a weighting mechanism similar to Hysteretic Q-learning (Matignon al.J (007). which places more importance joint actions. QTRAN can be viewed as a variant of WQMIX, which additionally uses the weight O for the joint Q-value whose target is smaller than the current estimate and the chosen action is not greedy. QTRAN approximates Q* as the target instead of the original target y and thus can deal with stochasticity. However, due to the 0 weight for overestimated Q-values, QTRAN is empirically hard to scale to more complex tasks (Samvelyan et af., 2 We also prove that there may not exist an appropriate weight when the targets are non- non-monotonic and stochastic.
better
In addition, there have been many developments in policy- based methods under CTDE settings. MAPPO (Yu et al., [021] applies PPO (Schulman et al., 2017] into MARL and shows strong empirical performance. However, Kuba et al. (2021) points out MAPPO suffers from instability arising from the non-stationarity induced by simultaneouslyy learning and exploring agents. Therefore, they introduce the multi-agent advantage decomposition lemma and the sequential policy update scheme to achieve monotonic improvement the joint policy, which converge to one of the Nash Equilibriums. However, the monotonic target in value decomposition methods can be interpreted as static multivariable optimisation problem, where there are non-optimal solutions that cannot be improved upon by coordinate descent. The sequential policy update scheme cannot guarantee convergence the optimal in this optimisation problem (Bertsekas) 2019).
Relationship To Reward Shaping. Reward shaping is a common technique for improving single- agent learners' performance by integrating expert knowledge into MDP (Gullapalli & Barto 1992). It also has been adopted to the MARL setting in recent work (Devlin et al. [011] Xiao et al. 2021).
Since it is not always possible to find an expert with complete domain knowledge, is not easy to set rewards for complex MARL tasks in advance. Therefore, adaptively shaping the reward is more attractive way. Some reward randomisation methods (Gupta et al., 2021| Tang et al. 2021) are proposed to convert the original MDP to new MDP with random rewards through universal successor features. However, these methods require a massive number of randomisation to find desirable reward function because they cannot guarantee policy invariance. GVR (Wan al. 2022) proposes inferior target reshaping and superior experience replay to eliminate the non-optimal self-transition nodes, which is similar to WQMIX and ignores the stochasticity of the transition. Compared with these methods, UTS is more efficient because it can perfectly represent the expected value for stochastic targets and guarantee policy invariance during target shaping.
EXPERIMENTS
In this section, we conduct empirical experiments to answer the following questions: (1) Is UTS better than the existing methods when the target is seriously non-monotonic? (2) Can UTS perform well when the target is mon-monotoiic and stochastic? (3) Can UTS perform efficient coordination in challenging multi-agent tasks? We compare UTS with value decomposition baselines, including
7

---

Under review as a conference paper at ICLR 2023
VDN Sunnhag et al., 2018),
QMIX (Rashid al., 2018), QTRAN (Son al. 2019). QPLEX (Wang Rashid et al. 2020) on a matrix game, a multi-agent Markov De- staattor-stagharee and StarCraft II aggtt-
et al. 2020a) and W WQMIX
cision Process, predator-pres
(Son et all] [201), 2019). We also conduct ablation studies (Appendix ( and compare Challenge (Samvelyan et al.
2022) and WQMIX with different weights (Appendix [D) as well as UTS with GVR (Wan al.]
more CTDE-based algorithms (Appendix E. More detailed experimental settings are included in
Appendix F
6.1 MATRIX GAMES
In this subsection, we consider a matrix game in Figure 3d, where the local optimal is difficult to jump out due to the considerable miscoordination penalties and stochastic reward. The optimal joint strategy is to perform (ut, u²) simultaneously. We adopt a uniform exploration strategy to approximate the uniform data distribution and eliminate the challenge of exploration and sample complexity. As shown in Figure Ba. UTS and QTRAN can achieve optimal performance, while other algorithms fall into local optimum. CW-QMIX fluctuates dramatically and cannot converge to any policy, which is consistent with our analysis in Section 3.2
UTS
CW-QMIX
OW-QMIX
QPLEX
QTRAN
QMIX
VON
(a) non-monotonic game with stochastic reward.
+10
(b) A non non- mon-tonot MMDP with stochastic state transition.
The payoff matrix ats:
02
Peagla (Z.
u²
8
-12
-12
8
-12
-12
M8
-12
12/0
u²
-12
6
8.
-12
6
-12
6
300
20L
34
50c
Figure 3: Mean test return on a stochastic matrix game and an MMDP.
We also consider multi-agent Markov Decision Process (MMDP) with non-monotonic and stochastic targets in Figure Bp. This MMDP involves two agents, three actions and team reward. Two agents start at state 81 and explore extrinsic rewards for ten environment steps. The state transits from $1 to $2 with probability 50% and $3 with 50% if agents perform u = (uî u²) ) at $1, and remains unchanged otherwise. The team continually obtains deterministic reward of +10 and -10 at 82 and $3, respectively. In this task, since VDN, QMIX, and QPLEX estimates the stochastic targets well but cannot deal with the non-monotonicity, they converge to the suboptimal with the return of +60. The negative results for CW-QMIX and OW-QMIX show that they converge to the stochastic suboptimal due to the undesirable weights. By contrast, UTS and QTRAN can achieve optimal performance.
6.2 PREDATOR-PRES
Predator-prey (PP) is a partially observable environment containing eight predators (agents) and eight prey in 10 x 10 grid world. Each agent observes 5 sub-grid around it and can perform five actions, i.e., up, down, left, right, and catch. The team receives a miscoordination penalty when two agents surround a prey and only one tries to catch it. By contrast, they earn a bonus of 10 if they catch the prey simultancously. After a successful catch, the catching predators and prey will be removed from the grid. Figure -b shows that VDN, QMIX, and QPLEX fail to return positive returns with significant penalty because the penalty makes these methods underestimate the per-agent action value of the real optimal. CW- -W-QMIX and OW- QMIX can achieve positive test returns when the penalty is -2 because they place more weight on better joint actions. QTRAN can also solve this task through its regularisation terms. However, CW-QMIX, OW-QMIX, and QTRAN fail solve the task when the penalty is - 10, suggesting difficulties in choosing the pre-defined weight and the network architecture. By contrast, UTS solves tasks quickly and steadily in all penalty settings.
We extend predator-prey to a stochastic version named predator-stag-he eight predators, four stags and four hares. The agents receive the same miscoordination penalty in predator-pree prry when they try to catch stag. By contrast, a catch of hare results in non-deterministic reward, i.c., the probabilities of receiving SRE R+ and -SR are both 50%. As shown in Figure 4--d, VDN and QMIX can quickly recover the optimal policy when the penalty is 0 because they can
(PSH), which contains
8

---

Under review as a conference paper at ICLR 2023
accurately evaluate the stochastic reward. When the penalty is -2, VDN, QMIX, QPLEX, and WQMIX fail to solve this task. QTRAN also struggles with the suboptimal in this setting. By contrast, UTS takes advantage of the uncertainty estimation module to avoid overestimating the stochastic action values, and uses the shaping function to eliminate the adverse impact of the miscoordination penalty. Therefore, it learns quickly and reliably in these tasks. The detailed comparison between
UTS and WQMIX with different weights can be found in Appendix D
UTS
CW-QMIX
OW QMIX
QPLEX
QTRAN
QMIX
VDN
PP, Penalty
Penalty--10
(c) PSH, SR 12, Pesalt-
Namber of Captured Stugs
(d) PSH, SR-12, Penalty -2
to
Moan Lost Komu
Moin Tas/ Rotum
Captured '0
To
10
1o
0.25M
0.5M 0.75M
IM
0.25M
0.5M 0.75M
LM
0.25M 0.5M 0.75M
IM
0.55
0.5M 0.75M IM Timestups
Timestops
Timestops
Timosteps
Figure Mean test return on predator- prey and predator-stag-heee
6.3 STARCRAFT MULTI-AGENT CHALLENGE
We also compare UTS with baselines on eight hard and super hard maps in the decentralised micromanagement tasks in StarCraft Multi-Agent Challenge (SMAC) (Samvelyan et al., 2019).
Figure showws the improved performance of UTS, which indicates that the target shaping function can be applied to more general benchmarks.
UTS
CW-QMIX
OW-QMIX
QPLEX
QTRAN
QMIX
VDN
Mean Ton Rate
1000
(9) 2c vs 64g
Mean Lost Win Rate %
100
(b) MMM2
Menn Lost Win Rate %
100
(c) 3 w 52
Mean Tost Win Rate %
100
(d) 5m, vs 6m
80
80
80
80
60
60
60
60
40
40
40
40
20
20
20
20
3.5M
1.5M
0.5M
1.5M
2M
0.5M
1.5M
2M
0.5M
1.5M
2M
Timestops
Timestops
Timesteps
Timestops
Moan Tost Was Rale 55
100
(+) 955x_ vs_ 3952
Moan Fost Win Kate 9/
1o0
(8 10m, vs_ 11m
Moan Fost Win Rate 8/
100
(g) 6h, vs, Sa
Moan Post Win Rate 5/4
100
(h) corridor
80
-80
80
80
60
8
50
40
40
20
20
20
20
1M
2M
3M
4M
3kg
0.5M
IM Timestops
1.3M
2kg
2M
3M
4M
1M
2M 3M Timestops
4M
SM
Timestops
Timestops
Figure 5: Mean test win rate on SMAC tasks.
CONCLUSION AND FUTURE WORK
This paper presents uncertainty-based target shaping (UTS), which was inspired by analysing the limitation of Weighted QMIX. We prove that there may not exist an appropriate weighting function for Weighted QMIX recover the optimal policy when the targets are stochastic and non- monotonic. To solve this problem, UTS first identifies whether a target value is stochastic by predicting the standard deviation of the reward and the prediction error between the predicted and the target embedding of the following state. Then we propose shaping function to project original target values into the monotonic space that QMIX can represent by replacing the deterministic suboptimal target with the minimal best per-agent values. Empirical results demonstrate the improved ability of UTS to deal with the task with non- mon-moootonic and stochastic targets, as well as more complicated tasks. The assumption of "unique optimal policy" is required in our proofs. In the environment with multiple optimal, the more efficient exploration method could be considered, as opposed to the simplistic e-greedy exploration scheme we used in this paper.
9

---

Under review as a conference paper at ICLR 2023
REFERENCES
Sally Aladdin, Samah EI- Ta-Taayayy Mostafa M. Fouda, and Adly S. Tag Eldien. MARLA-SG: multi- agent reinforcement learning algorithm for efficient demand response smart grid. IEEE Access, 2210026-210633 2020.
Dimitri Bertsekas. Multiagent rollout algorithms and reinforcement learning. arXiv preprint arXiv:1910.00120, 2019.
Wendelin Böhmer, Vitaly Kurin, and Shimon Whiteson. Deep coordination graphs. In International Conference on Machine Learning, pp. 980-991. PMLR, 2020.
Yuri Burda, Harrison Edwards, Amos Storkey, and Oleg Klimov. Exploration by random network distillation. arXiv preprint arXiv: 12894, 2018.
Xinyue Chen, Zijian Zhou, Zheng Wang, Che Wang, Yanqiu Wu, and Keith Ross. Bail: Best- action imitation learning for batch deep reinforcement learning. Advances in Neural Information Processing Systems, 13:18833-18366 2020.
Armen Der Kiureghian and Ove Ditlevsen. Aleatory or epistemic? does it matter? Structural safety, 31(2):105-112, 2009.
Sam Devlin, Daniel Kudenko, and Marek Grzeš. An empirical study of potential-based reward shaping and advice in complex, multi-agent systems. Advances in Complex Systems, 14(02): 251-278, 2011.
Jakob Foerster, Gregory Farquhar, Triantafyllos Afouras, Nantas Nardelli, and Shimon Whiteson. Counterfactual multi-agent policy gradients. In Proceedings of the AAAI conference artificial intelligence, volume 32.1, 2018.
Jakob N Foerster, Yannis M Assael, Nando de Freitas, and Shimon Whiteson. Learning to commu- nicate with deep multi-agent reinforcement learning. In Proceedings of the 30th International Conference Neural Information Processing Systems, pp. 2145-2153. 2016.
Vijaykumar Gullapalli and Andrew G Barto. Shaping as method for accelerating reinforcement learning. In Proceedings of the 1992 IEEE international symposium on intelligent control, pp. 454-559. IEFE, 1992.
Tarun Gupta, Anuj Mahajan, Bei Peng, Wendelin Böhmer, and Shimon Whiteson. Uneven: Universal value exploration for multi-agent reinforcement learning. In International Conference on Machine Learning, pp. 3930-3941. PMLR, 2021.
Alex Kendall and Yarin Gal. What uncertainties do we need in bayesian deep learning for computer vision? Advances in neural information processing systems, 30, 2017.
Landon Kraemer and Bikramjit Banerjee. Multi-agent reinforcement learning as a rehearsal for decentralized planning. Neurocomputing, 190:82-94, 2016.
Jakub Grudzien Kuba, Ruiqing Chen, Munning Wen, Ying Wen, Fanglei Sun, Jun Wang, and Yaodong Yang. Trust region policy optimisation in multi-agent reinforcement learning. arXiv preprint arXiv:2109. 1251, 2021.
Sheng Li. Jayesh K Gupta, Peter Morales, Ross Allen, and Mykel J Kochenderfer. Deep implicit co- ordination graphs for multi-agen reinforcement learning. In Proceedings of the 20th International Conference on Autonomous Agents and MultiAgent Systems, pp. 764-772, 2021.
Anuj Mahajan, Tabish Rashid, Mikayel Samvelyan, and Shimon Whiteson. Maven: Multi-agent variational exploration. Advances in Neural Information Processing Systems, 32, 2019.
Anuj Mahajan, Mikayel Samvelyan, Lei Mao, Viktor Makoviychuk, Animesh Garg. Jean Kossaifi, Shimon Whiteson, Yuke Zhu, and Animashree Anandkumar. Tesseract: Tensorised actors for multi- agent reinforcement learning. In International Conference on Machine Learning, pp. 7301-7312. PMLR, 2021.
10

---

Under review as a conference paper at ICLR 2023
Laëtitia Matignon, Guillaume J Laurent, and Nadine Le Fort-Piat. Hysteretic q-learning: algo- rithm for decentralized reinforcement learning in cooperative multi-agent teams. In /EEE/RSJ International Conference Intelligent Robots and Systems, pp. 64-69. IEEE, 2007.
Frans A Oliehoek and Christopher Amato. A concise introduction to decentralized POMDPs. POMeD. Springer, 2016.
Frans A Oliehoek, Matthijs TJ Spaan, and Nikos Vlassis. Optimal and approximate q-value functions for decentralized pomdps. Journal of Artificial Intelligence Research, 32:289-333 -3333, 2008.
Tabish Rashid, Mikayel Samvelyan, Christian Schroeder, Gregory Farquhar, Jakob Foerster, and Shi- mon Whiteson. Qmix: Monotonic value function factorisation for deep multi-agent reinforcement learning. 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. Advances in neural information processing systems, 33:10199-10210, 2020.
Mikayel Samvelyan, Tabish Rashid, Christian Schröder de Witt. Gregory Farquhar, Nantas Nardelli, Tim GJ Rudner, Chia-Man Hung. Philip HS Torr, Jakob N Foerster, and Shimon Whiteson. The starcraft multi-agent challenge. In AAMAS, 2019.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv: 2017.
Max Simchowitz and Kevin G Jamieson. Non-asymptotic gap-dependent regret bounds for tabular mdps. Advances in Neural Information Processing Systems, 32, 2019.
Kyunghwan Son, Daewoo Kim, Wan Ju Kang, David Earl Hostallero, and Yung Yi. Qtran: Learning to factorize with transformation for cooperative multi-agent reinforcement learning. In International Conference on Machine Learning, pp. 5887-5896. PMLR, 2019.
Peter Sunehag, Guy Lever, Audrunas Gruslys, Wojeiech Marian Czarnecki, Vinicius Zambaldi, Max Jaderberg, Mare Lanctot, Nicolas Sonnerat, Joel Z. Leibo, Karl Tuyls, et al. Value-decommosition networks for cooperative multi-agent learning based on team reward. Proceedings of the 17th International Conference Autonomous Agents and MultiAgent Systems, pp. 2085-2087, 2018.
Zhenggang Tang, Chao Yu, Boyuan Chen, Huazhe Xu, Xiaolong Wang. Fei Fang, Simon Shaolei Du, Yu Wang, and Yi Wu. Discovering diverse multi-agent strategic behavior via reward randomization. In International Conference on Learning Representations, 2021.
Lipeng Wan, Zeyang Liu, Xingyu Chen, Xuguang Lan, and Nanning Zheng. Greedy based value representation for optimal coordination in multi-agent reinforcement learning. In Proceedings of the 39th International Conference on Machine Learning, volume 162, pp. 22512-22535. PMLR, 17-23 Jul 2022.
Jianhao Wang, Zhizhou Ren, Terry Liu, Yang Yu, and Chongjie Zhang. Qplex: Duplex dueling multi-agent q-learning. In International Conference on Learning Representations, 2020a.
Jianhao Wang, Zhizhou Ren, Beining Han, Jianing Ye, and Chongjie Zhang. Towards understanding cooperative multi-agent q-learning with value factorization, 2021.
Tonghan Wang, Heng Dong, Victor Lesser, and Chongjie Zhang. Roma: Multi-agent reinforcement learning with emergent roles. arXiv preprint arXiv:2003.08033) 2020b.
Tonghan Wang, Tarun Gupta, Anuj Mahajan, Bei Peng, Shimon Whiteson, and Chongjie Zhang Rode: Learning roles to decompose multi-agent tasks. arXiv preprint arXiv:2010.01523. 2020c.
Yihan Wang, Beining Han, Tonghan Wang, Heng Dong, and Chongjie Zhang. Dop: Off-policy multi- agent decomposed policy gradients. In International Conference Learning Representations, 2020d.
Baicen Xiao, Bhaskar Ramasubramanian, and Radha Poovendran, Shaping advice in deep multi-agent reinforcement learning. arXiv preprint arXiv:2103. 15941, 2021.

---

Under review as a conference paper at ICLR 2023
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. In International Conference on 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. CoRR, abs/2002.03939, 2020b.
Xinghu Yao, Chao Wen, Yuhui Wang, and Xiaoyang Tan. Smix (A): Enhancing centralized value func- tions for cooperative multiagent reinforcement learning, IEEE Transactions on Neural Networks and Learning Systems, 2021.
Chao Yu. Akash Velu, Eugene Vinitsky, Yu Wang, Alexandre Bayen, and Yi Wu. The surprising effectiveness ppo in cooperative, multi-agent games. arXiv preprint arX1v:2103.01955, 2021.
Meng Zhou, Ziyu Liu, Pengwei Sui, Yixuan Li, and Yuk Ying Chung. Learning implicit credit assignment for cooperative auett- reinforcement learning. Advances in Neural Information Processing Systems, 33:1 111111831111100 11864, 2020.
Ming Zhou, Jun Luo, Julian Villella, Yaodong Yang, David Rusu, Jiayu Miao, Weinan Zhang, Montgomery Alban, IMAN FADAKAR, Zheng Chen, et al. Smarts: An open-source scalable multi-agent rl training school for autonomous driving. In Conference on Robot Learning, pp. 264-285. PMLR, 2021.
A OMITTED PROOFS
A.1 WVDN AND WEIGHTED LINEAR REGRESSION PROBLEM
WVDN operator is defined as
IW = arg min
Σ
wow (s, (s,u)(u(s, Qroe u))?
(9)
Qeae Qias
ueU
where Qlof = (Qroel Qror u) Eo Qals, Un), Qa(s, E RJ. ( u) is the optimistic weighting:
[
y(s,u) > Qcoc(s.
w w u)
(10)
a
otherwise
The optimising process of WVDN can be constructed weighted linear regression problem:
min W| VpT (Ax b)ll:
(11)
where A E xmm xmm, Run w.p.b E Rm" m,n E Z+, In particular, m dentoes the action space size for each agent, n denotes the number of agents.
Denote A = w vp A, bd
T
The optimal solution is:
w.
(12)
where A t
V T is the ascudo-inverss of " according to the Singular Value Decomposition.
U E Rm" xm and V E Rmmx mm are real orthogonal matrices, St E IR""" is diagonal matric with non-negative real numbers on the diagonal.
The proof is trivial.
Consider the full exploration scheme (i.e., e-greedy exploration with = 1), and the non-moneee non-monotonic game in Figure 6b, where 8, b - c 6.
12

---

Under review as a conference paper at ICLR 2023
For VDN (a special case of WVDN where 1), have
0
8
1
0
0
0
0
Qi(s, u
12
0
0
Qi(s,
12
0
1
0
00000
12
Qi(8,
A
1
0
x
Q2(8,ug)
b
6
w
(13)
0
1
0
0
6
Q2(s,
0
0
1
12
Q2(s,
0
0
6
0
0
6
According to 12
1 the optimal solution is
== (-4.44
0.89
0.89
-4.44
0.89
0.89)
(14)
Clearly, Qi(ut) < max (Ixx((()))) (1,2), which indicates that VDN fails to converge
the optimal.
A.2 OMITTED PROOFS IN SECTION 3
WVDN operator is defined in Section A.I
Denote the joint action [M1, i-th action of ua.
May Un]. where n is the number of agents. Denote uy as the
Consider matrix games in Figure Suppose the training dataset is fixed and the data has e-greedy distribution, where the greedy action is (uf, uz) and e E (0, 1].
Based on the e-greedy distribution, the probabilities of each joint action p(uj, w!) is:
(i,j) E (3.1 (3,3)),
9
Pr(ut, u²))
(3
2c)²
(i.j) (2,
(15)
9
33 2c)c
otherwise.
9
U2
14
14
14
24
T4
14
21
a
u3
u13
6
213
-12
23
b
b
c/d
x
6
12/0
6
u13
-12
12/0
6
23
b
u3
u3
u3
(a) A non-monnen monotonic matrix game.
(b) A stochastic matrix
(c) Payoff of
(d) Payoff of stochastic and non-montoniic game.
game.
stochastic matrix game.
Figure Payoffs of matrix games. (a) is a non-monotonic matrix game, where a > c > b; (b) is stochastic matrix game, where (uf. ug) receives with probability p and d with (1 p). e> > a > max(b, d, e} and a >> pc+ (1- p)d; (c-d) are two numerical examples for stochastic matrix games, where the reward in (c) is monotonie and in (d) is non-monotonie.
To recover the optimal policy, the weight a for WVDN is bounded by and the reward space. We start by analysing the matrix game in Figure op. Since the matrix game only involves one state, omit s for the input of value functions in the tollowing proofs.
Proposition 1 For WVDN, the weight should be smaller than 3e(e-c)+e((e-b) optimal joint policy on the non-monotonic matrix game in Figure 0z.
to recover the (e-3)
13

---

Under review as a conference paper at ICLR 2023
Proof. First compute the gradient for Q(4)), Q(1)))((()
vQ(u)) _[(e + (3 (3-
=cQ(((?)
ca a(3 c]b]
(16)
vQ(u)) = (3 20)a
9 +1
cb (3 - c)d
(17)
vQ(u)) = aa
ob - (3 t)c
(18)
g
Let vQ(ut) vQ( vQ(ut) =
Q(u+) + a(3 -e}b {Q (3 2e (c) ca(((n))
(19)
++ 30 aa
Q(a)) Q( = eb + (3 - f)c 1 (Q (12) + Q (3 - 2e Q()
(20)
3
To recover the optimal joint policy, the following conditions should be satisfied:
Q(u²) (a(((() > 0, Q(ub) max(Q(u²), Q(u))) >
(21)
Denote = c 3a ca. Then
Q(u ((x
+ - - -3
(3-22l) (e))a(((3 -
cb
+ (3- -)c c(Q(u)) Q(u))) (3 Q())
3
t ca- 30
(9 -3-3e)o- el
6 6 3
Q(ub) + =aa
b+
(22)
3t
Let Q(u)) max((((x))))))) Q({)) 0 and Q(1)) ((x()(
0.
(c(a-c)+((c-b)) (e-3)=(e-b)
Then <
Proposition 2 For WVDN, the weight a should be large enough to recover the optimal joint policy for the stochastic matrix game in Figure 6p.
Theorem Let lWVVDQQ := arg mino EQ!- EnEo wor (Q,{ss (ror(s,u)) u))² and wow (s, u) is the optimistic weighting from 44. for any E (0, 1].
Then 3Q such that arg max IwwVDNQ f arg max Q
Proof. Since the proof of Proposition 2 and Theorem contains significant overlap. we will merge them both into a single proof.
First compute the gradient for Q(4)),
vQ(u+)
9 [[( + 3a - (())) (3 -3- 2e)aQ(12)) + caQ(())
6a a(3 c)b]
(23)
3 2
vQ(
- [18--2)(11-0))---0000111----1111 Q(())
9
+ (3 - 2e) + -ad
-ab cab (3 - 2c) (pc ad - apd) cac)
(24)
vQ( 9 + Q(1)))))))))))))(())))))))))QQ + - -3 Q())
ca
(3 t)e]
(25)
To recover the optimal joint policy, the following requirements should be satisfied:
Q(u+) max ( Q(1)))) Q(1b) max(Q(u)), Q(+2)) 0
14

---

Under review as a conference paper at ICLR 2023
Let (Q(4)) vQ(u)) = vQ(uf) 0. Denote c+ 3a co, (3 13-220 -2c)(1 a)p + 3a. Then
Q(u))-Q(uu) - Q((()) <
+a+
(3- 33=
ECx
(b + e)
(3 2c)p
--2e)((1 - p)ar d (26)
t
m
m
- -(u))-Q(u)) < aa
c
+
(3 c)a
6 (3 c)p
(27)
3
For the matrix game in Figure 6
ob, consider the following situations:
(1) The target is monotonic but stochastic. For example, in Figure 6c. = 8, == 6, 12, ==0 O, and p = 0.5. To recover the optimal joint action, the weight a should be greater than (0.434, 0.667, 0.827, 0.932) when (1, 0.75, 0.5, 0.25), respectively.
(2) The target is non non-monotonic and stochastic. For example, in Figure 6 a = 8, 12, c = 12, d = 6, and p 0.5. When = (1, 0.7, 0.5, 0.25), there does not exist the weight (0, making Q(ul) - max (Q(uf), (( > 0, i.e., WVDN cannot converge to the optimal.
Thus, OE such that arg max Q & arg max Q for any a E (0, 1]. D
More experimental results can be found in Appendix B.I
A.3 OMITTED PROOFS OF RESHAPING FUNCTION
Theorem 2 Let Q and Qf be the orignal and the shaped action value based on 7 Then Vs S and Vu E U such that arg max, Q(s, u) is unique, arg max, Q (s, = arg max, Q u) and Q' (s,u) E Q
Proof. Considering only fully-observable setting for ease of representation. Thus notations do not distinguish the concepts of states and observation-action histories. In addition, when more than one optimal policy exists, most Q-learning algorithms fail converge a stable point (Simchowitz
& Jamieson 2019 Wang et al. 2020a; Rashid et al. 2020). Thus, consider a 8 E S, we assume
" arg max, (s, u) unique.
Assume maxg (s,, uas u_a) for all un are perfectly represented.
Then ((s, < min,e A {maxu.. Q(s, uay u-a)}.
By the shaping function from 77p:
[ Q'(ss, ub) = Q(5, u²)) Q'(s, min(max Q(8, ui, u.),, Vu: u + up and u, u
(28)
u_:
Under the assumption of the unique optimal action, we have Q' u²) > (s for all u & up- Therefore, arg max, Q1(s,, u) = arg max, Q(s, u).
Suppose (f. Q1 u1), .... Qn, u,,)) = Q (s. Vu (U), u,,) E U. Then fs(s, Qu.)) (-a(ua)) min max (ss, tay u-a), max Q(s, us u 1) Vi E -a
u_.
fa(s, Qu Q-a (u_a) a)) = min(max Q(s, V/ u_a), max Q(s, s, Us 1i, -a (29)
u_
where Q-a(u = (Q,(s, 4z) ui)ii-a
Let Qo Qs u()) if maxn_. ((s, uo u.)) max Q(s, u/a u-a), Va E A.
Then, according to 29) [s, (ua), Q (u_))) > fa(s, Qa(u)), Q-a (u(u))))
Thus we can find (s, (8, u1), .... Qn(s, un)) to represent Q (s. u), Vu (MI,..., E U, > 0. And so ( (s.u) u) E Queef Vs S, U.
where 8fa 3Q_
Now talk about the case of multiple optimal. When more than one optimal policy exists in the Markov Decision Process, many value-based algorithms fail to converge on a stable point (Simchowitz)
& Jamieson 2019). However, multiple optimal may be very common in multi-agent setting. For
15

---

Under review as a conference paper at ICLR 2023
example, when two agents arrive crossroads, the optimal solution is that one of them chooses to move and another chooses to make way. In this situation, the team can solve this simple task no matter which agent chooses to move.
34
M4
24
02
14
1
0.5
0.75
0.75
0.74
0.75
0,95
0.95
245
0.5
145
0.76
0.76
1
0.74
0.75
145
0.97
0.97
(a) Payoff of a game with multiple optimal.
(b) QMIX,
1.
(c) VDN,
=1
(d) UTS,
1.
02
02
02
ui]
14
U2
x]]
0.95
0.96
0.92
0.93
24]
0.73
0.76
0.61
0.65
243
0.96
1.02
xx3
0.92
1.02
243
0.76
1.01
0.66
1.00
(e) UTS, =
0.75.
(1) UTS,
0.5.
(g) UTS, 0.25.
(h) UTS, 0.05.
Figure 7: (a) The payoff matrix for game with multiple optimal. (b-h) The estimated joint Q-values Qtot returned from QMIX, VDN, and UTS with different exploration rate. Boldface means the optimal joint action from the payoff matrix, or the greedy joint action from the Qtot-
We take a simple one-step matrix game with multiple optimal as an example. The payoff matrix is shown in Figure We investigate the performance of VDN, QMIX, QPLEX, and UTS this simple task. Since this matrix game is non-monotonic, the target values cannot be perfectly represented in Q!" and @m=es. When the full exploration scheme (i.e., e-greedy with e 1) applied, none of these methods can converge to the optimal. Although QPLEX achieves the full representational capacity (i.e., the joint Q-values Que the same as the payoff), it still cannot converge because all per-agent Q-values are optimal (because of the solve this problem by e-greedy with decayed c. In particular, we show the Qtor returned from UTS to illustrate the effect of the e. As shown in Figure Ze-h, can see the gap between the suboptimal and optimal increases with the decrease of the e, which improves the learning stability. However, UTS inherits the characteristic of QMIX and thus is not contraction, i.c., it would return two distinct Qiot and converge to any one the optimal.
However, in practice, we can
B RESULTS ON MATRIX GAMES
B.1 WQMIX WITH DIFFERENT WEIGHTS
demonstrate the complete data of minimal 1/a a for WVDN and WQMIX to recover the optimal policy, where a denotes the weight on the suboptimal. The payoff matrix is shown in Gh. The dataset is collected by the e-greedy exploration, where the greedy action is set to u (uf. uz!
In Section 3.1
CHAQUIX
CHA-NNIX
WYDK
Aggnn Quec
LE
10 The porfenzzaoe with difioett -lanea -12 1125.
(8) T2e porferrzacc diticeet
(c) TCTTTealte betricnn the real optinal sadans and Bacipnaly adiin.
(8) The Indicattr Fancton Eat Shows
wheae
windlar ta gpnncly addin sptinud.
Figure 8: (a)-(b) shows the performance of WVDN and WQMIX on the non-monotonic game in Figure oh. and (c)-(d) shows the performance on the non monotonic and stochastic game in Figure Th
We select a = 8, b = 12, and (I) three reward assignments, c E {-3, 3, 6). e = 0.25, as well as (2) three exploration rate assignments, E {0.5, 0.75, 1). c 6, and run WVDN and WQMIX with five random seeds on a fixed dataset. We show the gap between the approximated real optimal action value Q (uf) and greedy action value (ūT) for agent 1, which should be zero if the algorithm converges to the optimal. Figure 8h-b shows that the gap reduces with the increase of //, indicating
16

---

Under review as a conference paper at ICLR 2023
that the weight should be small enough to deal with non-monotonicity. In addition, we can that a should be small enough to converge to the optimal when the suboptimal value is large or the exploration rate is low, which is consistent with our analysis.
we prove that the contradiction of the choice a may result in converging on the suboptimal for WOMIX. We also conduct experiments verify our analysis. We consider the matrix game in Figure Dh, and train WVDN and WQMIX on a fixed dataset. The dataset collected by the e-greedy exploration, where the greedy action is u (wi, wz) and e 0.5. We show the gap between the approximated real optimal action value Q1 (uf) and greedy action value Q1 (2f) for agent 1, which should be zero the algorithm converges to the optimal. We also show whether the greedy action is optimal by indicator function Qx())))-(())))
In Section and Section A.2
As shown in Figure B -dd WQMIX and WVDN cannot converge the optimal with different a when the payoff is non monotonic and stochastic. Since CW-QMIX does not place on the current greedy joint action, it can get rid of the stochastic suboptimal u" when u' is the current greedy action, i.e., = uu" However, with the decrease of Q.n (u') CW-QMIX falls into this suboptimal again once of u². Therefore, in Figure Sd, CW-QMIX cannot converge to the optimal, which is consistent with our analysis.
that the gap between Qi (uf) and Q1 (ūī) is tiny. However, as shown
)
B.2 THE APPROXIMATED JOINT ACTION-VALUES
We also show the joint Q-value returned from our baselines on a matrix game with non-monone non-monotonic and stochastic rewards in Figure 9a. We adopt uniform exploration strategy to approximate the uniform data distribution (i.e., 6-greedy exploration with = 1). As shown Figure 9 UTS and
QTRAN recover the optimal policy, while other methods fail solve this simple task. Since
have discussed QMIX and WQMIX in previous sections, here we analyse QPLEX and GVR.
D
14
14
3
0
u
24
ui
U2
u1
U:
M4
2
-12
-12
1.68
1.68
1.68
u3
2.72
2.72
2,72
u5
-12
-0
6
245
1.68
168
6.33
u/
2.72
5.97
5.97
u
-12
2
6
1.68
6.33
5.93
u
2.72
5.97
5.97
()
game with NOn com-oontoonic and stochastic rewards.
(b) UTS.
(c) OW-QMIX (o==0.1).
(d) CW-QMIX (a 0.1)).
U2
un
uf
M
u
14
M
u]
14
-8.29
-8.29
-8.29
5,31
5.33
5.33
a!
8.09
-2..32
-12.24
4.37
-8.06
-8.45
-8.29
1.49
1.64
u/
5,35
6.0B
6:B
ax3
-12322
-2.77
5.76
u/
-6.93
1.61
4.37
-8.29
5.00
8:15
5.35
6.03
6.03
2x3
-12.24
5.76
5.62
-8.09
4.37
4.37
(e) QMIX (c=1).
(f) GVR.
(g) QTRAN.
(h) QPLEX.
Figure 9: The results on matrix game with non-monotonic and stochastic rewards. Boldface means the optimal joint action from the payoff matrix, or the greedy joint action from the Qtot-
In QPLEX, the joint Q-value is:
Qrae(T, u) Vio((T) + Atoe(T,
Σ
Vi(T) + Σ Ar(T,u)Att (,),,
1=1
(wx(T) [.(T)) + Σ Ar(T ((TT -V(TT)
(30)
where Vi(T.) = max,, Qi w.), w,(T) 2 0, u)) >
Let = [u],..., uf, ..., ] u² juf.... ,.,,,, n1l denote the optimal and one of the suboptimal joint action, where n is the number of agents. If QPLEX is initialised to this joint action, i.e., Vioe(T) Σi= Qi(T, u,), it is difficult jump out from this suboptimal for QPLEX. Consider Q(s, u') ) is the real second greatest action value at given state, where uf * uf, Vi E A. Therefore, joint Q-values whose targets smaller than Qual (T, u²) can be perfectly represented by QPLEX
17

---

Under review as a conference paper at ICLR 2023
However, when (T, u²) is sampled, QPLEX tries minimising the following loss:
Ar (T..T,, - uu) Vioe ((o0())))
(31)
where Q(T, (T) > 0. decreases to almost zero, and Q,(T, gradually reaches to Vi(T). However, the process is very time consuming and (; u,) cannot exceed (T) in most cases due to the low weight AT u"),
(T( 0, and A,(T, 0. As result, ^, u²)
i.., the vanishing gradient problem. Consequently, as shown in Figure 2 the approximated joint Q-values for the optimal u* (u), wh) and three suboptimal {(ug u (w) (u] ug) are 4.37 in QPLEX.
GVR uses inferior target shaping and superior experience replay eliminate the non-optimal self- transition nodes. However, it ignores the stochasticity at all as WQMIX, and thus behaves as CW-QMIX and cannot converge to any joint action (Figure 9D. More comparison among GVR. WQMIX, and UTS can be found in Appendix D
C ABLATION STUDIES
In this section, we conduct ablation studies to investigate the influence of target shaping in UTS. The following methods are included in the evaluation: 1) QMIX, which is the natural ablation baseline of UTS, 2) UTS without target shaping (denoted by UTS-wo-TS), i.c. agents are trained only according to the best action value function (s, Tax ua), 3) UTS without the reward predictor (denoted by UTS-wo-R), 4) UTS without the state predictor (denoted by UTS-wo-S), and 5) the original UTS.
C.1 THE REWARD AND THE STATE PREDICTORS
First, we investigate the role the reward and the state predictors. We compare UTS-wo-R, UTS- wo-S, and UTS on matrix game (stochastic non-monotonic rewards), multi-agent Markov Decision Process (MMDP) (stochastic state transition and non- non-monotonic returns), predator-pry prey (deterministic non-monotonic returns), and predator-stag -are (stochastic monooonoo returns). As shown in Figure TO UTS-wo-R cannot cope with stochastic rewards and thus fail to solve matrix game, MMDP, and predator-stag-hare UTS-wor S--- cannot identify whether the state-action pair leads stochastic transition and fail to solve MMDP. However, since predator-pri prey only involves deterministic targets, the target shaping function does not overestimate the suboptimal. As result, both UTS-wo-P and UTS-wo-S can solve predator-prey, indicating the effectiveness of the target shaping function.
UTS
UTS-wo-R
UTS-w0-8
(o) Matrix Game
(b) MMDP
(c) PP, penalty-110
Nunber of Caytune Stags
(di PSH, SR-12 Penalty
80
Mein lst Ketumn
Mean Kerum
Moan Est Metun
30
10
bv d
40
0
10k
20%
30k
40k
50k
30k
40k
0.25M
0.5M
0.75M
IM
0.25M
0.5M 0.75M IM
Figure 10: The comparison of UTS UTS-wo-S, and UTS.
The additional models (the reward and the state predictors) in UTS are introduced identify stochasticity, which are necessary to cope with any target state-action values. When the task does not involve stochasticity, UTS learns slower because the target shaping function relies on the results from these models. When we have complete domain knowledge of the task, suitable threshold for the model prediction error can be set to improve the learning speed.
C.2 THE TARGET SHAPING FUNCTION
Now show the effectiveness of the target shaping function. We compare QMIX, UTS-wo-TS and UTS on predator-prey and predator-stag-hat hare. As shown in Figure since the miscoordination penalty is large, QMIX cannot deal with non-monotonic targets and thus fail to solve these tasks.
18

---

Under review as a conference paper at ICLR 2023
and UTS can learn to catch the prey (stags), whereas UTS learns more quickly. Since the estimated best action value introduces additional estimation error that may cause a significant variance, also show the standard deviation of per-agent action values Qa As shown in Figure we can see that UTS has a lower standard deviation than UTS-wo-TS.
To better understand why UTS can achieve better performance, first, discuss the advantage of value factorisation methods. Linear value factorisation implicitly achieves credit assignment using a counterfactual baseline (Wang et al. 2021). The individual Q-value function Qi(s, ue) is updated by:
Ey ~ (N, u4, u-.) n
En (8, u')] + wx))),
(32)
Y1
where the residue term w = [w](s] (s), ..., w. wn(s)) (s)] denotes an arbitrary vector satisfying Vs, Σ1 (s) = O. As result, the individual Q-value in linear value factorisation can be viewed as type of advantage function, where the per-agent baseline reduces variance but does not affect the convergence. Due to the non-linear mixing function in QMIX, more general theoretical understanding of monotonic value factorisation is still insufficient. However, previous work shows that QMIX also implicitly performs credit assignment and outperforms linear value factorisation RRahiid et al. 2018 2020
Zhou et al., 2020).
UTS
QMIX
UTS-wo-T8
Number of Capeured Stags
(a) PP. Penaltym.10
Number Captured Stogs
(b) PSH. SR-15, Pemaly
Stankard Deviations
Stmmbed Dovaatinss
1.5
5
7.0
1.0
5
0.25M 0.5M 0.5M
IM
0.25M
0.5M 0.75M
IM
0.25M 0.5M 0.75M Timestops
IM
0.25M 0.5M 0.75M IM
Timesteps
Timesteps
Timestops
Figure 11: The comparison of QMIX, UTS, and UTS-WO-TS.
Qi (4))
(uf)
(x))
(a) Payoff matrix,
(b) QMIX.
UTS.
(d) UTS-wo-TS.
Po-Ageu Actim Valuzs
Par Agrt Actim Valuus
0.5
PS- Agant Action Valuss
0
-5
m
-0.5
-12
1200
-10
-12
8
-15
-20
-1.5
10k Timesiqps
15k
20k
10k Timesteps
15k
20k
10k Tlimestops
15k
20k
Figure 12: Per-agent action values from QMIX, UTS, and UTS-wo-TS.
numerical example provided Figure T2 Figure T2p shows the payoff of one-step mon-monotoiic game. First, show the standard deviation per-agent action values Qa- QMIX con-
UTS
QMEX
1TTS-w0-T
verges the suboptimal when it meets non-monotonic targets of
Standand Devuttioss
R.0
the joint Q-value function. As shown in Figure 12b. Q (ut)
6.0
keeps reducing and is smaller than the values of other actions, which implies that QMIX converges the suboptimal due representational limitation. Both UTS and UTS-wo-TS --- can re- cover the optimal policy. The action values in UTS-wo-TT show similar trends, and thus UTS-wo-TS can be stable until it per- fectly approximates all action values. By contrast, UTS shapes the targets to ensure they can be represented by monotonic value factorisation, where the optimal policy is invariant during this shaping. UTS performs credit assignment with the shaped targets, the action values in UTS can be viewed as a type of advantage and thus much smaller than UTS-ww-TT The action values in
4.0
2.0
5k
10k
15k
20k
Timesigg
Figure 13: Standard deviation of per-agent action values from on
QMIX, UTS, and a random 10 x 10 matrix game.
19

---

Under review as a conference paper at ICLR 2023
((TT((t) (u²) and Q4 are negative UTS show two different trends, where Q (ut) is positive, Q
when the algorithm converges.
We also show the standard deviation of per-agent action values from QMIX, UTS, and UTS-wo- on a random 10 x 10 matrix game, where the suboptimal is filled with random numbers generated uniformly between -20 and 19, and the unique optimal value is +20. As shown in Figure UTS reduces variance compared to UTS-wo-TS, thus improving learning efficiency and stability.
D THE COMPARISON WITH WQMIX AND GVR
In Section 3.1 we prove that WQMIX with a low a can overcome any non-monotonic tasks. However, also prove that WQMIX is particularly brittle with stochasticity because overestimates the expected value of the suboptimal whose target is large with a low probability. GVR also ignores the stochasticity and cannot accurately identify whether a given action is inferior. As result, WQMIX with fine-tuned a and GVR are able to solve any non non-monotonic targets, but cannot deal with stochasticity.
UTS
CW-QMIX(a-D91> CW-QMIXia- 0.000)
OW-QMIX(a-AL) OW-QMIX Q.0))
OW-QMIX((-0000)
CW-QMIX(a--00 0.1)
GVR
(Penalyy-))
(b) PP
(Penatyy
PP (Penalty 10)
40
40
40
Mean tow sterom
Mean Tont Kortm
Moan Toe Rasm
-00
Mozn Tos Ranm
-30
20
200
0.25M
0.5M
3.75M
IM
0.55M
0.5M
0.75M
0.25M
0.5M
0.5M
IM
0.25M 0.5M 0.75M
IM
Timatage
Timolaps
Timesiqu
Timenios
(6) PSIT (Panally-))
(0 PSI (Penalyy 2)
(21 PSH (Pesaly--)
(8) PSII (Penahy--10)
Numbe Caprured Stags
Number of Capoord Stgss
Namboz of Caquurd Stus
Nambes of Capuurd Stuss
50
2.
0.25M
0.5M
0.75M
IM
0.25M
0.5M
0.75M
IM
0.25M
0.5M
0.75M
IM
0.25M
0.5M
0.75M
IM
Timesaps
Timesteps
Timestops
Timestops
Figure 14: The comparison of GVR, UTS, and WQMIX with different weights.
To further show the difference between these methods and UTS, we compare them on predator-prey with different level of miscoordination penalties and stochasticity. Figure [4 demonstrates that WQMIX with very low and GVR can obtain the positive test return in all penalty settings on predator-prey. However, they cannot recover the optimal joint policy on stochastic predator stagor--------e hare. By contrast, UTS outperforms WQMIX and GVR in these tasks.
E THE COMPARISON WITH MORE ALGORITHMS
We also compare our method with more algorithms to further show our motivation. We consider recent multi multi-agent reinforcement learning works, including RODE (Wang et al. 2020c), MAPPO (Yu
et al. 2021) and HAPPO (Kuba et al. 2021).
Figure 15 shows that RODE, MAPPO, and HAPPO fail to recover the optimal policy in the matrix game and the MMDP with stochastic and non- -o-mooottoncc targets, where the payoff is shown in Section 1. In addition, they also cannot solve predator-prey and predator-stag-hart when the penalty is large. This is because that RODE applies the same monotonic mixing network QMIX and thus can only represent values in the restricted monotonic space. This representational limitation makes RODE cannot cope with monoooooonii targets. MAPPO is an independent learning approach with many valuable techniques, but cannot deal with these tasks due to the non-stationarity of the environment. HAPPO applies agent-by-agent update scheme and improves the performance
20

---

Under review as a conference paper at ICLR 2023
compared to MAPPO. This update scheme can only guarantee convergence one of the Nash Equilibriums in theory (each agent is treated to receive the equal reward under the team reward static setting). However, the monotonic target in value decomposition methods can be interpreted multivariable optimisation problem, where there are non-optimal solutions that cannot be improved upon by coordinate descent. The sequential policy update scheme cannot guarantee convergence to the optimal in this optimisation problem (Bertsekas) 2019). Or we can also view the task of a Pareto Selection problem, and HAPPO cannot ensure convergence to the real optimal (the Pareto optimal) and thus fail to solve these tasks.
predator-prey and predator-stag-hate
The representational limitation of monotonic value decomposition will not necessarily result in converging to suboptimal. We can see that RODE outperforms UTS in some SMAC maps. However, UTS still achieves comparable performance with RODE in many SMAC tasks, indicating that the target shaping function is more general than the weighting function in WQMIX.
UTS
MAPPO
HAPPO
RODE
Matrix Came
(b) MMDP
(e) PP, Penalty
Number of Captured Stags
(c) PSHL SR-12, Penalty
Mean les Return x
-0
Mean Tes Return
30
-20
40
Tou
10
18
-10
-20
10k
20k
30%
40k
50%
10%
20k
30%
40k
50%
0.25M 0.5M 0.75M
IM
0.25M 0.5M 0,75M IM
Timeslops
Timeslops
Timesteps
Timestops
Mcan Jest Win Ruce 1
100
(e) 2e 642g
Mean lest Win itac %
100
(1) conidor
Mean Jest Win itaee %
100
(g) 6h, vs 82
Moan Test Win itase %
100
(b) Sea, 6m
-0
-00
-00
30
60
60
60
60
40
40
40
40
20
20
20
20
1.5M
2M
4M
5M
4M
SM
1.5M
2M
Timostops
Timosteps
Timosteps
Timostops
Figure 15: The performance of UTS, RODE, MAPPO, and HAPPO on matrix game, MMDP, predator- prey, predator-stag-hant and many SMAC maps.
The sampling efficiency of MAPPO and HAPPO is lower than Q-learnin based algorithms because they on-policy algorithms. Therefore, Figure 15p-h shows their poor performance compared with RODE and UTS with limited environment steps. Not that we use SC2. 4..44.6 6.2. 69232 (the version of StarCraft II which VDN, QMIX, and RODE used in their papers) instead of SC2 4. 1.0 (the version which pasecy-based algorithm always used). Performance is not always comparable between versions.
We emphasise that our work is to provide a concrete analysis of the relationship between the non- monotonic and stochastic targets and the monotonic value decomposition. We propose target shaping function to eliminate the adverse impact from representational limitation, where the approximation of all original targets is not required. The shaping function project all original targets to a monotonic space and keeps the optimal policy unchanged. Since all shaped targets are tractable to monotonic value decomposition, QMIX can recover the optimal policy with any original target. That to say, we relax the monotonic assumption of the relationship between the joint Q-value and individual Q- Q-values.
F EXPERIMENTAL SETUP
We adopt the same architecture for VDN, QMIX, QTRAN, QPLEX, and WQMIX as (Samvelyan
ct al.) 2019 Rashid et al. 2020). Each agent independently leams policy with fully shared parameters between all policies. We used RMSProp with a learning rate of 5 x 10-4 and y = 0.99, buffer size 5000, mini-bated size 32 for all algorithms. We use c-greedy strategy, and is linearly annealed from to 0.05 over 50k timesteps (unless specified otherwise). The dimension of each agent's is GRU hidden state is set to 64.
For WQMIX, we use a = 0.1 on predator predator-prey and predator-stag haae (unless specified otherwise), and 0.5 in SMAC.
21

---

Under review as a conference paper at ICLR 2023
For UTS, the same agent and mixing network in WQMIX (Rashid et al. 2020). For the reward and the state predictors, we use a multilayer perceptron (MLP) with ReLU non limearttie and gated recurrent unit (GRU) to extract features, where the hidden dim is 128. Then we another MLP to output the predicted reward, the standard deviation and the embedding of the next state. The first and the GRU parameters shared. The dimension of the target embedding for the state m is set to 16. We use Adam with learning rate of 1 x 10 to train the predictors. For the best Q-value function, we use feed-forward networks with three hidden layers of dim {64, 64) and ReLU non- non-linearities, where the optimiser is RMSProp with learning rate of 5 x 10
We conduct experiments on an NVIDIA RTX 3090 GPU. Each task needs train for about hours on predator-pre prey, and about 8 to 16 hours on SMAC, depending on the number of agents and episode length limit of each map. We evaluate 32 episodes with decentralised greedy action selection every 10k timesteps for each algorithm.
We use an c-greedy policy in which decreases from to 0.05 over 1M timesteps for 3s52_vs_3s6z, 6h_vs _8 and corridor, and over 50k timesteps for others.
All the learning curves the experiments are plotted based on five training runs with different random seeds using mean and standard deviation with confidence internal 95%.
22


Reviews:
[{"review_id": "aP5aaOoJWM", "reviewer": "Reviewer_kwZB", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes a new value factorization method for cooperative MARL. The technique brings out an alternate way of value factorization (to WQMIX and QMIX) when the target values are non-monotonic and stochastic. In particular, prior approaches is the inability to recover the optimal Qtot value when the joint value function is non-monotonic and stochastic. A popular matrix game example variant shows that the previous approaches frequently overestimate or underestimate joint Q values in stochastic and non-monotonic settings. An alternate shaping function is introduced to generate the shaped joint action-value that can consider the stochasticity in the reward and state function and place appropriate weight on the different joint actions. To this end, a neural network is trained to predict standard deviation and error in the reward and the embedding of the next state. Another neural network is trained to estimate the best action value for each agent, assuming the agent gets the cooperation of other agents. Finally, based on the prediction error and the best action values, the shaping function generates monotonic target joint action-values for QMIX.", "summary_of_the_review": "A paper with strong empirical performance but room for improvement in the throughness and clarity of the exposition.", "strength_and_weaknesses": "Strengths\n•\tIncorporates stochasticity in reward and state representation\n•\tGood empirical performance\n•\tLimitations of prior works is explained through theory and the example of matrix game\n\nWeaknesses\n•\tThe overall approach is a bit of a kitchen sink with many hyperparameters to be tuned and models to be trained. QMIX alone is already known for being challenging on this front with larger number of agents.  See, e.g., the below reference.\n•\tGoal of estimating the stochasticity of rewards and next states seems similar in spirit to distributional RL, but there is no comparison to related work from this literature.\n•\tWhile the experiments include some ablations, the role of various parts of the overall approach is not fully explored.  For example, there are two approaches used in combination to detect stochasticity (reward predictor and state predictor).  What if you only include one?  Or what happens if you use different rules about when to apply or not apply the change of target than that in Equation (7) since at the very least it has two different cases.\n\n@article{avalos2021local,\n  title={Local Advantage Networks for Cooperative Multi-Agent Reinforcement Learning},\n  author={Avalos, Rapha{\\\"e}l and Reymond, Mathieu and Now{\\'e}, Ann and Roijers, Diederik M},\n  journal={arXiv preprint arXiv:2112.12458},\n  year={2021}\n}\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "Q4p2mtFo4Xd", "reviewer": "Reviewer_9h2R", "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": "", "summary_of_the_paper": "The submission proposes a new CTDE algorithm called UTS. UTS is designed to have two properties that the submission calls policy invariance and full representational capacity. The submission benchmarks UTS in matrix games, predator prey, and SMAC.", "summary_of_the_review": "The method feels a little hacky to me, but I think that's not the worst thing if it performs well. \n\nThe submission makes big claims about its method's performance, such as \"outperforming state-of-the-art\". However, I do not feel that it lives up to these claims in the experiments, both because it is lacking in baselines and because it does not follow modern deep RL benchmarking practices.", "strength_and_weaknesses": "### Clarity\n\nI personally found the description of the problems that UTS is trying to solve somewhat obfuscated. Perhaps I am not the target audience and that is why I found it difficult to follow, but I think the submission could be clearer overall. To give a concrete example, I feel like I read through the whole intro without really understanding the main idea.\n\n### Baselines\n\nIt seems like the submission is lacking some relevant baselines, such as MAPPO, IPPO, and HATRPO, given that it is claiming to \"outperform state-of-the-art\".\n\n### Benchmarking\n\nIn deep RL, and perhaps especially deep MARL, there is historical precedent for bad empirical practices, such as reporting mean return over a small number of seeds. It is well documented that this practice leads to unreliable reporting of algorithmic strength -- see Deep Reinforcement Learning at the Edge of the Statistical Precipice (NeurIPS 2021). I think the submission ought report the alternative metrics advocated in the statistical precipice paper if it wants to make big claims like \"outperforming state-of-the-art\".\n\n### Motivation\n\n> In this section, we introduce a shaping function to generate the shaped joint action-value Qf(s, u) to replace the original Q(s, u). The shaping function should have the following properties: 1) policy invariance, i.e., not making the agent deviate from the true goal and keeping the optimal policy unchanged; 2) full representational capacity, i.e., all shaped joint action-values should belong to\na subset of Qmvf.\n\nThis is a really important sentence in the submission. Yet, it doesn't feel clear to me. What does \"not making the agent deviate from the true goal\" mean? Additionally, why are we saying that \"shaped joint action-values should belong to a subset of Qmvf\"? Isn't belonging to a subset of a set the same as belonging to the set itself?\n\n### Dealing with stochasticity\n\nThe approach to determining whether stochasticity is present feels unsatisfactory to me. The state predictor may output zero even if there is stochasticity.\n\n### Confusion\n\n> However, these approaches suffer from instability arising from the non-stationarity of the environment induced by simultaneously\nlearning and exploring agents (Kuba et al., 2021). Centralised learning of joint action-values can solve these problems, but it is challenging to scale in real-world applications due to intractably large joint action space and communication constraints. \n\nKuba et al. (2021) show that MAPPO-style approaches lack a monotonic improvement guarantee. Unless I am misunderstanding, UTS does not have such a guarantee either. Could the authors clarify this point?", "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": "DutBHniwGV", "reviewer": "Reviewer_gapB", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes a reward shaping scheme for MARL towards fixing QMIX, an existing algorithm suffering from suboptimality in non-monotonic settings. The method uses target shaping by predicting reward and next state uncertainty. ", "summary_of_the_review": "Interesting idea but needs improvements (see the 2 sections above).", "strength_and_weaknesses": "1. There are some important works missing in the related works which need to be discussed towards getting a proper context for learning in CTDE settings (instead of focusing only on value based methods) eg. : Tesseract [1] an actor-critic method natively supports decentralization despite environment stochasticity and non monotonicity, it also proves important representation capacity results. Similarly, there have been developments in model based methods [2] for addressing representational issues.\n\n2. How does the proposed method deal with uncertainty arising from neural network approximation? this is a huge component of target noise in practise. There isn't enough discussion on this given that the proposed method relies on uncertainty estimates that too with limited number of environment steps.\n\n3. What is meant by \"convergence to the optimal QMIX for any non-monotonic and stochastic Q\"? is it the best qmix learnable policy?\n\n4. How exactly is eq 7 preventing a bad monotonic projection? There needs to be a guarantee in probabilisitic or worst case sense.\n\n5. Why are stronger baselines not used for comparison? For eg. [3] has better performance on all the SMAC maps considered here. Overall this also affects significance of the work if strictly better methods already exist.\n\n6. The paper claims to be aimed for stochastic domains but SMAC is not adequately stochastic.\n\n7. The paper needs improvement in terms of writing and presentation, especially for conveying the overall problem and method. Currently, I do not find it easily readable.\n\nMinors:\n1. The results used from other works should be cited where they are used: eg. The line in introduction \"However, QMIX can only represent values in the restricted monotonic space\" should cite Maven, Mahajan et al 2019 and Qtran, Son et al 2019, there itself.\n2. Eq 3 has been repeated twice.\n3. Pg.5 ending, \"objection of\", did you mean \"objective of\"?\n\nReferences:\n1. Tesseract: Tensorised Actors for Multi-Agent Reinforcement Learning, Mahajan et al, 2021\n2. Model based Multi-agent Reinforcement Learning with Tensor Decompositions, Van Der Vaart et al 2021\n3. Rode: Learning roles to decompose multi-agent tasks, Wang et al, 2021\n", "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": {}}]

Author rebuttal:

Decision: Reject