UneVEn: Universal Value Exploration for Multi-Agent Reinforcement Learning
Authors: Tarun Gupta
Anuj Mahajan
Bei Peng
Wendelin Boehmer
Shimon Whiteson
Venue:  (2021)
Keywords: multi-agent reinforcement learning
deep Q-learning
universal value functions
successor features
relative overgeneralization

Abstract: This paper focuses on cooperative value-based multi-agent reinforcement learning (MARL) in the paradigm of centralized training with decentralized execution (CTDE). Current state-of-the-art value-based MARL methods leverage CTDE to learn a centralized joint-action value function as a monotonic mixing of each agent's utility function, which enables easy decentralization. However, this monotonic restriction leads to inefficient exploration in tasks with nonmonotonic returns due to suboptimal approximations of the values of joint actions. To address this, we present a novel MARL approach called Universal Value Exploration (UneVEn), which uses universal successor features (USFs) to learn policies of tasks related to the target task, but with simpler reward functions in a sample efficient manner. UneVEn uses novel action-selection schemes between randomly sampled related tasks during exploration, which enables the monotonic joint-action value function of the target task to place more importance on useful joint actions. Empirical results on a challenging cooperative predator-prey task requiring significant coordination amongst agents show that UneVEn significantly outperforms state-of-the-art baselines.

Under review as a conference paper at ICLR 2021
UNEVEN: UNIVERSAL VALUE EXPLORATION FOR MULTI-AGENT REINFORCEMENT LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
This paper focuses on cooperative value-based multi-agent reinforcement learn- ing (MARL) the paradigm of centralized training with decentralized execution (CTDE). Current -fh-----rthhtttttt art value-based MARL methods leverage CTDE to learn centralized joint-action value function as a monotonic mixing of each agent's utility function, which enables easy decentralization. However, this mono- tonic restriction leads to inefficient exploration in tasks with nonmonotonic re- turns due to suboptimal approximations of the values of joint actions. To address this, we present novel MARL approach called Universal Value Exploration (Un- eVEn), which uses universal successor features (USFs) to learn policies of tasks related to the target task, but with simpler reward functions in a sample efficient manner. Vnn uses novel action-selection schemes between randomly sampled related tasks during exploration, which enables the monotonic joint-action value function of the target task place more importance on useful joint actions. Em- pirical results on challenging cooperative predator-prey task requiring significant coordination amongst agents show that Vnn significantly outperforms state- of- of-the-art baselines.
INTRODUCTION
Learning control policies for cooperative multi-agent reinforcement learning (MARL) remains chal- lenging as agents must search the joint-action space, which grows exponentially with the number of agents. Current state-of-the--rt value-based methods such as VDN (Sunehag et al. (017)) and QMIX (Rashid al. 2020b) learn a centralized joint-action value function as a monotonic factorization of decentralized agent utility functions and can therefore cope with large joint action spaces. Due to this monotonic factorization, the joint-action value function can be decentrally maximized as each agent can simply select the action that maximizes its corresponding utility function.
This monotonic restriction, however, prevents VDN and QMIX from representing nonmonotonic joint-action value functions (Mahajan et al. 2019) where agent's best action depends on what tions the other agents choose. For example, consider a predator-prey task where at least three agents need to coordinate capture prey and any capture attempts by fewer agents penalty of magnitude p. As a result, both VDN and QMIX tend to get stuck in a suboptimal equi- librium (also called the relative overgeneralization pathology, Panait al.] 2006 Wei et 2018) in which agents simply avoid the prey (Mahajan et al.) 2019 Böhmer et al. 2020). This happens for two reasons. First, depending on p. successtul coordination by at least three agents needle in the haystack and any step towards it is penalized. Second, the monotonically factorized joint- action value function lacks the representational capacity to distinguish the values of coordinated and uncoordinated joint actions during exploration.
penalized with
Recent work addresses the problem of inefficient exploration by VDN and QMIX due to monotonic factorization. QTRAN (Son et al.] 2019) and WQMIX (Rashid et al. 2020a) address this problem by weighing important joint actions differently, which can be found by simultaneously learning a centralized value function, but these approaches still rely inefficient e-greedy exploration which may fail on harder tasks (e.g., the predator- serdatto--reyyyaoo task above with higher value of p). MAVEN (Ma- hajan et al. 2019) learns ensemble of monotonic joint-action value functions through committed exploration by maximizing the entropy of the trajectories conditioned on a latent variable. Their exploration focuses on diversity in the joint team behaviour using mutual information. By contrast,

---

Under review as a conference paper at ICLR 2021
this paper proposes Universal Value Exploration (UneVEn), which follows the intuitive premise that tasks with a simpler reward function than the targer task (e.g. a smaller miscoordination penalty in predator-prey) can be efficiently solved using a monotonic factorization of the joint-action value function. Therefore, UneVEn samples tasks related to the target task, that are often easier to solve, but often have similar important joint actions. Selecting actions based these related tasks dur- ing exploration can bias the monotonic approximation of the value function towards important joint actions of the target task (Son et al., 2019; Rashid et al. (020a),, which can overcome relative over- generalization. To leverage the policies of the sampled related tasks, which only differ in their reward functions, Vnn uses Universal Successor Features (USFs, et al., 2018) which have demonstrated excellent zero-shot generalization in single-agent tasks with different reward func- tions (Barreto et al., 2017, 2020). USFs generalize policy dynamics over tasks using Universal Value Functions (UVFs, [Schaul et al., 2015), along with Generalized Policy Improvement (GPI, Barreto et al. 2017). which combines solutions of previous tasks into new policies for unseen tasks.
Our contributions are as follows. First, propose Multi-Agent Universal Successor Features (MAUSFs) factorized into novel decentralized agent-specific SFs with value decomposition net- works (Sunchag al., 2017) from MARL. This factorization enables agents to compute decentral- ized greedy policies and to perform decentralized local GPI, which is particularly well suited for MARL, as it allows to maximize over combinatorial set of agent policies. Second, we propose Universal Value Exploration (UneVEn), which uses novel action-selection schemes based on re- lated tasks to solve tasks with nonmonotonic values with monotonic approximations thereof. We evaluate our novel approach in predator-pree tasks that require significant coordination amongst agents and highlight the relative overgeneralization pathology. We empirically show that Une VEn with MAUSFs significantly outperforms current state-of-theearr art value- based methods on the target tasks and in zero-shot generalization (Borsa et al.) 2018) across MARL tasks with different reward functions, which enables us to leverage Une effectively.
BACKGROUND
Dec-POMDP: A fully cooperative decentralized multi-agent task can be formalized as a decentral- ized partially observable Markov decision process (Dec-POMDP, OOlihhoek et al.) 2016) consisting of a tuple G = (s, P. R, 22 O,,,)). s E S describes the true state of the environment. At each time step, each agent a E A = n. chooses an action u² E U. forming a joint action u E E = U This causes a transition in the environment according to the state transition kernel P(s'Is, 2) S x u x S + (0. 1]. All agents are collaborative and share therefore the same reward function R(s, u) S x U - IR and 7 E 10, is a discount factor.
Due to partial observability, each agent cannot observe the true state s, but receives an observation o" E Ω drawn from observation kernel 0 ~ ((8, a). At time f, each agent a has access to its action-observattin history 7f Ti (Ω x 21) x Ω on which it conditions stochastic policy (ut (Tf.. E TT" denotes the histories of all agents. The joint stochastic policy π T(u (st, T:) = HH it (ut (((TT)) induces a joint-action value function Q" Tr, un) E [Ge|st, TE, Wn], where G. Ei=o "Tee+ is the discounted return.
We adopt the framework of centralized training and decentralized execution (CTDE Krae- mer& & Banerjee 2016), which assumes access to all action-observation histories T, and global state 8, during training, but each agent's 'ss decentralized policy T can only condition on its own action- observation history 7 This approach can exploit information that is not available during execution and also freely share parameters and gradients. which improves the sample efficiency considerably (see e.g., (oerster et al. 2018 Rashid et al.) [0206] Böhmer et al. 2020).
CTDE:
Value Decomposition Networks: A naive way to learn in MARL is independent Q-learning (IQI., Tan 1993), which learns an independent action value function Q* ui; (a) for each agent that conditions only on its local action-observall agents' information in CTDE, value decomposition networks (VDN, [Sunehag et al. 2017) repre- sent the joint-action value function Qtot as a sum of per-agent utility functions Q": Qroe! u; 0) Σm= (T" u²: Each Q" still conditions only on individual can be represented by agent network that shares parameters across all agents. The joint-action value function Qtat can be trained using Deep Q-Networks (DQN, Mnih et al.) 2015). Compared to VDN, QMIX (Rashid et al. 2020b) allows joint-action value function Qiot to be represented as
history TØ. To make better use of other
histories and
2

---

Under review as a conference paper at ICLR 2021
nonlinear monotonic combination of individual utility functions. The greedy joint action in both VDN and QMIX can be computed decentrally by individually maximizing each agent's 's utility. See OroojlooyJadid & Hajinezhad 2019)) for more in-depth overview of cooperative deep MARL.
Task based Universal Value Functions: In this paper, we consider tasks that differ only in their reward functions Ry (s. u) w Φ(ss, u), which are linear combinations of set of basis functions Φ : S x U + Rd Intuitively, the basis functions & encode potentially rewarded events, such as opening door or picking up an object. We use the weight vector to denote the task with reward function Rw. Universal Value Functions (UVFs, (UVFs,|Schaul et al., 2015) is an extension of DQN that learns a generalizable value function conditioned on tasks. UVFs are typically of the form (st, ue w) to indicate the action-value function of task w under policy π at time t as:
Qa (st, Ue w) = E Σ n2 (wo(s Us+4) St, ut] = E Σ r2
Ø(5t+e u(ts) w st. uz) (1)
Successor Features:
The Successor Representation (Dayan 1993) has been widely used in single-
agent settings (Barreto et al. 2017 2018 Borsa et al. (2018) to generalize across tasks with given reward specifications. By simply rewriting the definition of the action value function Q (st, Ue w) of task w from Equation
[ ww have:
Q (=1 Ue w) = ET
((344is Ue++) 81, Ue
w
(5,,,,, (1)) w
(2)
where (s, u.) are the Successor Features (SFs) under policy x. For the optimal policy σ of task 2, the SFs T6 summarize the dynamics under this policy, which can then be weighted with any reward vector w E Rd to instantly evaluate policy x²= on it: Q*= ut w) = u) w.
Universal Successor Features and Generalized Policy Improvement: Borsa al. (2018) intro- duce universal successor features (USFs) which learns SFs conditioned on tasks using the general- ization power of UVFs. Specifically, they define UVFs of the form Q(s,, u, 2, w) which represents the value function of policy TT evaluated on task E Rd These UVFs can be factored using the SFs property (Equation 2) as: Q(s, u, Z, w) = (ss, u, 2) w. where (s, u, 2) are the USFs that generate the SFs induced by task-specific policy Tz One major advantage of using SFs is the ability to efficiently do generalized policy improvement (GPI, |Barreto et al.) 2017). which allows a new policy to be computed for any unseen task based on instant policy evaluation of a set of policies on that unseen task with a simple dot-product. Formally, given set C C Rd of tasks and their corresponding SFs {1b(s, u. 2EC induced by corresponding policies (==)zEC, new policy a' for any unseen task w E Rd can be derived using:
(s) E arg max max Q(s, u, w) uel
arg max max (b u.z) 2) T
xEC
uel
sEC
Setting C = {w] allows us to revert back to UVFs, as we evaluate SF' induced by policy Tw on task w itself. However, we can use any set of tasks that are similar to w based on some similarity distribution D(-lw). The computed policy T' guaranteed to perform no worse on task than each of the policies { Jzec (Barreto et al. 2017). but often performs much better. SFs thus enable efficient use of GPI, which allows reuse of learned knowledge for zero-shot generalization.
3 MULTI-AGENT UNIVERSAL SUCCESSOR FEATURES
In this section, we introduce Multi-Agent Universal Successor Features (MAUSFs), extending single-agent USFs (Borsa et al.) 2018) to multi-agent settings and show how we can learn gen- eralized decentralized greedy policies for agents. The USFs based centralized joint-action value function Qtoe (T, u. x, w) allows evaluation of joint policy πे = {T...... TT) comprised of local agent policies 2 of same task z on task w. However, each agent may execute a different policy r2. of different task za E C, resulting in combinatorial set of joint-policies. Maximizing over all combinations Σ = (z',..., ".....,))) 2²) E C should therefore enormously improve GPI. To enable this flexibility, we define joint-action value function (Qroe) of joint policy T {Tī )=ec evaluated on any task w E Id as: Qeoe (T, u, ह, w) = vitor (T, u, )) w. where ( u, 2) are the MAUSFs of (T, u. summarizing the joint dynamics of the environment under joint policy πy. However, train- ing centralized MAUSFs and using centralized GPI to achieve maximization over a combinatorial
space of z becomes impractical when there are more than handful of agents, since the joint action
3

---

Under review as a conference paper at ICLR 2021
((0")t) Kaacc I
sesu(w)
UneVEn exploration
Proe(Te sovufu)
MLP
u (w)
Cusscale
probabality at
C2 [w)
GRU
y D w)
[6% m.)
[1(0.2)
zcolice)
and with a): (w)
GaelFeer 2g. (v)
Co (k Uni(v)}
vrtria of s
Au /eeUJ(w) (w)
MAUSFs training
Figure 1:
Schematic illustration of the MAUSF's training and UneVEn exploration with GPI policy.
space (4) and joint task space (C") of the agents grows exponentially with the number of agents. To leverage CTDE and enable decentralized execution by agents, we therefore propose novel agent- specific SFy for each agent following local policy T which condition only its own local action-observation history and task z".
Decentralized Execution: We define local utility functions for cach agent as (*" u², x", w) " u², ;2;0) w. where "p" , u², ==; 0) are the local agent-specific SFs induced by local policy TT. (u² (u²(ra) of agent a sharing parameters 0. Intuitively, Q" @T wa 2", w) is the utility function for agent when local policy T2a (u"|r") (7") of task z" is executed on task w. We use VDŇ decomposition represent MAUSFs thror as sum of local agent-specific SFs for each agent a:
(4) We can now learn local agent-specific SFs 20d for each agent that can be instantly weighted with any task vector GPI policy in decentralized manner.
Qroe u. 2, w) Σ
Σ
;) w 2/tor (T, 2u, w. Tw.
Rd generate local utility functions Q", thereby allowing agents to use the
Decentralized Local GPI:
Our novel agent-specific SFs allows each agent to locally perform decentralized GPI by instant policy evaluation of set C of local task policies { Jasec on any unseen task w to compute local GPI policy. Due to linearity of the VDN decomposition, this is equivalent to maximization over all combinations of = (z) (zt...., z") E C x C = C" as: (T)
E
arg max max Qioe u. uEu EEC"
{arg max max 46" (7" u", =0) w w)"= (5)
ElEll 2"EC
As all of the above relies on the linearity the VDN decomposition, cannot be directly applied to nonlinear mixing techniques like QMIX (Rashid et al. 2020b).
Training: MAUSFs for task combination are trained end-to-end by gradient descent on the loss:
L( x)
E.B [ss u:) + rattor (T--1, 2; throt (Tr. ur z: 0)[[
(6)
where the expectation is over a minibatch of samples {(E, ur T.) from the replay buffer B (Lin 1992]. 0 denotes the parameters of a target network (Mnih et al. 2015) and joint actions ugg
n [u Ja=1 are selected individually by each agent network using the current parameters (called arg max " 1. u, ;)) 2" Each agent learns therefore local agent-specific SFs "0"(7" ur, 2; () by gradient descent on L(A, z) for all C vu {w)) where D(-[w) is drawn from a distance measure around target task The green region of Figure]] [ shows a CTDE based architecture to train MAUSEs for given target
Double Q-learning, van Hasselt et al. 2016); uza
task w. A detailed algorithm present in Appendix
UNEVEN
In this section, present Une (red region of Figure Dp. which leverages MAUSFs and decen- tralized GPI to enable efficient exploration on the target task w. The joint-action value function of the target task suffers from suboptimal approximations due monotonic factorization. At
4

---

Under review as a conference paper at ICLR 2021
the beginning of every exploration episode, we sample set of related tasks v {2 ((-ww) w)); containing potentially simpler reward functions, from a distribution D around the target task. The basic idea is that some of these related tasks can be efficiently learned using monotonic joint-action value function. These tasks will therefore be solved early and exploration will concentrate on state- actions that are useful to them. As the sampled tasks more weight on the important joint actions of the target task (Rashid et al. 2020a). This implicit weighting allows the learning of the joint-action value function of the target task to focus on accu- rately representing the value of the more important joint actions, and thereby overcome the relative overgeneralization pathology.
},
similar w, this has the potential to put
Many choices for D are possible, but in the following we sample related tasks using a normal dis- tribution centered around the target task u E TRd with a fixed variance a as DD - N(wr, oIa). The resulting task vectors weight the basis functions & differently and represent different reward func- tions. In particular the varied reward functions can make these tasks much easier, but also harder, to solve with monotonic value functions. However, the approach has the advantage of not requiring any domain knowledge. The consequences of sampling harder tasks on learning are discussed with the corresponding action-selection schemes below.
Action-Selection Schemes: Vnn uses two novel schemes to enable action selection based on related tasks. To emphasize the importance of the target task, we define a probability of selecting actions based on the target task. Therefore, with probability 1 the action is selected based on the related task. Similar other exploration schemes, a is annealed from 0.3 to 1.0 in our experiments over fixed number of steps at the beginning of training. Once this exploration stage is finished (i.e.,
= 1), actions are always taken based on the target task's joint-action value function. Each action- selection scheme employs local decentralized GPI policy, that maximizes over a set of policies = based on = E C1 (also referred to as the evaluation set) to estimate the Q-values of another set of tasks & E C2 (also referred to as the target set) using:
("( (.2,k)
Uh = 2 = arg max max max
o6 (T(" u, 2) k "EAAA
wEM kEC, zEC,
Here Ci DU {w) is the set of target and related tasks which induce the policies that are evaluated (dot-product) on the set of tasks Cz. which varies with different action-selection schemes. The red box in Jillustatsss Vnn exploration. For example, Q-eearning always picks actions based on the target task, i.e., the target set C2 = [w]. However, this scheme does not favour important joint scheme target GPI and execute it with probability a.
actions. We call this default We now propose two novel action-selection schemes based on related tasks with probability a, and thereby implicitly weighting joint actions during learning.
At the beginning of each episode, this action-selection scheme uniformly picks one related task, i.e., the target set C2 (k ~ Uniform(v)) ), and selects actions based on that task using the GPI policy throughout the episode. This uniform task selection explores the learned policies of all related tasks in D. This works well in practice as there are often enough simpler tasks to induce the required bias over important joint actions. However, if the sampled related task is harder than the target task, the action-selection based on these harder tasks might hurt learning on the target task and lead to higher variance during training.
Uniform GPI:
Greedy GPI: At every time-step this action-selection scheme pieks the task k vU(w) that gives the highest Q-value amongst the related and target tasks, i.e., the target set becomes C2 = v (w)- Due to the greedy nature of this action- setiionselection scheme, exploration is biased towards solved tasks, as those have larger values. We are thus exploring the solutions of tasks that are both solvable and similar the target task w. which makes them great candidates for important joint actions of w.
NO-GPI:
To demonstrate the influence of GPI on the above schemes, we also investigate ablations, where we define the evaluation set C₁ {k} to only contain the currently estimated task k, i.c., using U = {uf = arg max maxkec, 2b" (Tf u, k; 0) KoEA for action selection.
5 EXPERIMENTS
In this section, we evaluate Une on a variety of complex domains. For evaluation, all exper- iments are carried out with five random seeds and results shown with + standard error across
5

---

Under review as a conference paper at ICLR 2021
seeds.
We compare method against number of SOTA value-based MARL approaches: IQL
Tan 1993), VDN (Sunchag et al. 2017), QMIX (Rashid et al. 2020b), MAVEN (Mahajan et al.
2019
WQMIX (Rashid al. 2020a). QTRAN (Son et al. 2019 and QPLEX (Wang et al. 2220a
Domain 1 m-step matrix game
We first evaluate UneVEi on m-step matrix game proposed by Mahajan et al. (2019). This task is diffi- cult to solve using simple e-greedy exploration poli- cies as committed exploration is required to achieve the optimal return. Appendix [+] shows the m-step matrix game from Mahajan et al. (2019), in which
Mean Teat Return
13
12
11
10
OPLEX OTRAN
UwwVtn-Unfee---G
MAVEN
VON
the first joint decision of two agents determines the
Brendy
maximal outcome after another m- 1n-1 decisions. One initial joint action can reach a return of up to m + 3, whereas another only allows for This challenges monotonic value functions, as the optimal joint reward function of the first decision is nonmono- tonic. Figure 2 shows results of all methods on this task for m = 10 after training for 35k steps. action selection scheme converges to an optimal re- schemes outperforms all other methods, which suffer from poor c-greedy exploration and often learn to take the suboptimal action in the beginning. Due to the nonmonotonicity of the initial state, it becomes difficult to switch the policy later, leading to suboptimal returns and only rarely converging to optimal solutions.
8.0
5.0
10.0
15.0
[thousands)
20.0
25.0
30.0
35.0
Figure 2: Baseline results for m 10.
Vnn with greedy (Une VEn- Sean-Greedy--Ge turn and both greedy and uniform (Une LEEE-Uniform-OO
Domain 2 Cooperative Predator-Prey
We next evaluate Une VEn on challenging cooperative predator- prey tasks similar to one proposed by Son al. (2019), but significantly more complex in terms of the coordination required amongst agents. We use a complex partially observable predator-prey prey (PP) task involving eight agents (preda- tors) and three prey that is designed test coordination between agents, as each prey needs to be captured by at least three surrounding agents with a simultancous capture action. If only one or two surrounding agents attempt to capture the prey, a negative reward of magnitude p is given. Success- ful capture yields a positive reward of +1. This task is challenging for two reasons. First, depending on the magnitude of penalty p, exploration is difficult as even a single agent miscoordinates, the penalty is given, and therefore, any steps toward successful coordination are penalized. Second, the agents must be able to differentiate between the values of successful and unsuccessful collaborative actions, which monotonic value functions can only do if all agents already act optimally. More details about the task are available in Appendix B
Proposition 1. For the predator-prey game defined above, the optimal joint action reward function for any group of 2 I k I n predator agents surrounding prey is nonmonotonic (as defined by Mahajan et al. 2019) iff 0. (Proof is provided in Appendix B
Simpler PP Tasks: We first demonstrate that both VDN and QMIX with monotonic joint-action value functions can learn on target tasks with simpler re- ward functions. To generate a simpler task, we re-
3.0
2.0
Teas
move the penalty associated with miscoordination, i.e. P = O, thereby making the returns monotonic. Figure 3sows that both QMIX and VDN can solve this task as there is no miscoordination penalty and the monotonic joint-action value function can learn to efficiently represent the optimal joint-action val- ues. Other SOTA value-based approaches (MAVEN, WQMIX and QPLEX) and Vnn with both uniform (Une VEn Min--nfform-GP1 and greedy (Une VineVEn-Gre VEn-Greedy-GPP) action-selecti schemes can also solve this monotonic target task.
1.0
0.5
101
OPLEX
MAVEN
OTRAN
VAN
0.0
1.0
2.0
3.0
4.0
5.0
6.0
7.0
8.0
(mll)
Figure 3: Baseline results for 0.
Harder PP Tasks: We now make the target task nonmonotonic by increasing the magnitude of the penalty associated with each miscoordination, i.e., p E {0.004, 0.008, 0.012, 0.016). For a smaller penalty of p 0.004, Figure 4 (top left) shows that VDN is still able to solve the task, further suggesting that simpler reward related tasks (with lower penalties) can be solved with monotonic approximations. However, both QMIX and VDN fail learn on three other higher penalty target

---

Under review as a conference paper at ICLR 2021
0.004
0.008
Ncan Text Return
Mean Test Return
2
MAVEN
OTRAN
VON
OMX
WwwVEn-Greedy-Gr
WOMOX
0..0
1.0
2.0
3.0
4.0
5.0
6.0
7.0
8.0
0.0
1.0
2.0
3.0
4.0
5.0
6.0
7.0
8.0
T (mll)
(mil)
0.012
0.016
Mean Test Raturn
2:
Mean Test Return
0.0
2.0
4.0
5.0
6.0
7.0
0.00
[mil)
(mil)
Figure 4: Comparison between Vn SOTA MARL baselines with p E {0.004, 0.008, 0.012, 0.016).
0.012
0.016
Mean Teat Raturn
2
Mean Test Return
Gready-GPi Grendy ROSH
Targen-CPI Targen moors
Uniform-GPP
uniform
6.0
2.0
3.0
4.0
5.0
6.0
7.0
1.0
[mil)
[mill
Figure 5: Ablation results: Comparison between different action selection of UneVEn for p E (0.012,
tasks due to their monotonic constraints, which hinder the accurate learning of the joint-action value functions. Intuitively, when uncoordinated joint actions are much more likely than coordinated ones, the penalty term can dominate the average value estimated by each agent's utility. This makes difficult to learn an accurate monotonic approximation that will select the optimal joint actions.
Interestingly, other SOTA value-based approaches that aim to address the monotonicity restriction of QMIX and VDN such as MAVEN, QTRAN, WQMIX and QPLEX also fail to learn on higher penalty tasks. WQMIX solves the task when = 0.004, but fails other three higher penalty target tasks. Although WQMIX uses an explicit weighting mechanism to bias learning towards important joint actions, it must identify these actions by learning nommonotonic value function first. An e-greedy exploration based on the target task will take a long time to learn such a value function, which is visible in the large standard error for p (0.008, 0.012, 0.016) in Figure 4 By contrast, both Une Siin-Uniformm GPI and MieVEE-Gredy--OO value functions more accurately and solve the task for all values of p. As expected, the variance of Une Uniform-GPP GPI is high on higher penalty target tasks (for c.g., = 0.016) as exploration suffers from action selection based on harder related tasks. Greedy GPI does not suffer from this problem. Videos of learnt policies are available at https:: gy rdwpo5
can approximate nonmonotonic
Figure shows ablation results for higher penalty tasks, i... p (0.012.0.016) To contrast the effect of UneVEn on exploration, we compare our two novel action-selection schemes to Mon-VF---rge---G show that Une Een--enTTaaae TEn-TTrgtt-GP fails to solve the higher penalty nonmonotonic tasks as the employed monotonic joint value function the target task fails to accurately represent the values of different joint actions. This demonstrates the critical role of Vnn and its action-selection schemes.
Ablations:
which only selects the greedy actions the target task. The results clearly
Next we evaluate the effect of GPI by comparing against Une VEn with MAUSFs without using the GPI policy, i.e., setting the evaluation set C {k} in Equation First, Une using NOGPI policy with both uniform (Uniforn-NOGP) and greedy (Greedy-NOGP) action selection outper- form TOGPe, further strengthening the claim that Un with its novel action-selection

---

Under review as a conference paper at ICLR 2021
scheme enables efficient exploration and bias towards optimal joint actions. Next, Figure 5 clearly shows that for each corresponding retion-selection scheme (uniform, greedy, and target), using a GPI policy (+-GPI) is always favourable it performs either similarly to the NOGPI policy (*- NOGPI) or much better. GPI appears to improve zero-soot generalization of MAUSFs across tasks, which in turn enables good action selection for related tasks during Une exploration.
Zero-Shot Generalization: Lastly, we evaluate this zero-shot generalization for all methods to check if the learnt policies are useful for unseen high penalty
Sero-Shot Generalization
2,25
2.7 2.08
Moan Test fatum
-1:24
-0.69
test tasks. We train all methods for 8 million en- vironmental steps on task with = 0.004, and
+3.77
111.1
test 60 rollouts of the resulting policies of all meth- ods that are able to solve the training task, i.e., EeeVennnnGdy-----e MAVEN, and WQMIX, on tasks with E {0.2, 0.5}. For policies trained with Une Gree-dddy- and
UneVEn-Greeddy-co UnaVEn-Uniform-GP
WOMIX
VON
MAVEN
VDN, UneVEn-Uniform-
0.2
0.5
Figure Zero-shot gencralization comparison; training on p = 0.004, testing on E (0.2, 0.5).
Une Seiin--niffom--eee GPI,
the NOGPI policy for
the zero-shot testing. i.e., C1 = C2 = [w]. Figure [ shows that Vnn with both uniform and greedy schemes exhibits great zero-shot generalization and solves both test tasks even with very high penalties. As MAUSFs learn the reward's basis functions, rather than the reward itself, zero-shot generalization to larger penalties follow naturally. Furthermore, using Vnn exploration allows the agents to collect enough diverse behaviour to come up with a near optimal policy for the test tasks. On the other hand, the learnt policies for all other methods that solve the target task with p 0.004 are ineffective in these higher penalty nonmonotonic tasks, as they do not learn to avoid unsuccessful capture attempts. More details about the implementations are included in Appendix C Additional ablation experiments are discussed in Appendix D
Domain 3: Starcraft Multi-Agent Challenge (SMAC)
We now evaluate Une VEn on challenging cooperative StarCraft II maps from the SMAC benchmark (Samvelyan et al. 2019). We consider SMAC maps where each ally agent unit additionally penal- ized for being killed or suffering damage from the enemy, in addition to receiving positive reward for killing/inflitinng damage on enemy units, which has recently shown to improve performance (Son)
et al. 2020). We present the results for one super hard map (MMM2, involving 10 units of 3 types), two hard asymmetric maps (5m_vs_5m and 10m_vs.1im) and three easy maps (2s32, 1c3s52 and 8m).
Figure 7 presents the mean test win rate for all maps. Both VDN and QMIX achieve almost 100% win rate these maps, which leads to conclude that they do not suffer from relative overgener- alization and that simple c-greedy policies suffices for these maps. Thus, the additional complexity of learning MAUSFs in our approach results in slightly slower convergence. However, VEn with both GPI schemes matches the performance as VDN and QMIX in most maps, with only small deviations in 5m_vs_6m. 6m6, demonstrating that our method can scale well to large complex tasks.
MMNG (Super Hard)
5m, AR, 6m Blard)
10m, ve, 31m (lerd)
100
300
60
60
23
20
9.6
6.
69
Im (Tasy)
2536 (Caes)
1chede (Teey)
100
100
Figure 7: Comparison between UneVEn, VDN and QMIX SMAC maps.
8

---

Under review as a conference paper at ICLR 2021
6 RELATED WORK
Improving monotonic value function factorization in CTDE MAVEN (Mahajan et al. 2019) shows that the monotonic joint-action value function of QMIX and VDN suffers from suboptimal approximations on nonmonotonic tasks. It addresses this problem by learning diverse ensemble of monotonic joint-action value functions conditioned on latent variable by optimizing the mutual information between the joint trajectory and the latent variable. Deep Coordination Graphs (DCG) (Böhmer et al.) 2020) uses a predefined coordination graph (Guestrin et al. 2002) to represent the joint-action value function. However, DCG is not fully decentralized approach and specifying the coordination graph can require significant domain knowledge, [Son et al. (201)) propose QTRAN that addresses the monotonic restriction of QMIX by learning a (decentralizable) VDN-factored joint-action value function along with an unrestricted centralized critic. The corresponding utility functions distilled from the critic by solving linear optimization problem involving all joint actions, but its exact implementation is computationally intractable and the corresponding approxi- mate versions have instable performance. QPLEX (Wang al., (020a) uses duplex dueling (Wang) iet al. 2016) network architecture to factorize the joint-action value function with linear decompo- sition structure. WQMIX (Rashid et al.) 2020a) Iearns a QMIX- joint-action value function along with an unrestricted centralized critic and proposes explicit weighting mechanisms to bias the monotonic approximation of the optimal joint-action value function towards important joint actions, which is similar to our work. However, in our work, the weightings are implicitly done through action-selection based on simpler reward related tasks, which are easier to solve.
Exploration There exists plethora of techniques for exploration in model-free single-agent RL,, based on intrinsic novelty reward (Bellemare et al., 2016 Tang et al.) (007), predictability (Pathak
ct al. 2017). pure curiosity (Burda et al. 2019) or Bayesian posteriors (Osband et al. 2016 Gal et al.
2017 Fortunato et al. 2018: O' O'Donoghue et al. 2018). In the context of multi-agent RL, Böhmer
et al. 2019) discuss the influence of unrelible intrinsic reward and Wang et al. (222bb) quantify
the influence that agents have on each other's s return. [Zheng & Yue (2018) propose to coordinate
al. (0188) investigate social motivations of competitive agents. However, these techniques aim to visit as much of the state-action space as possible, which exacerbates the relative overgeneralization pathology. Approaches that use state abstraction (e.g.. g.. Roderick et al. 2018) can speed up exploration, but only by restricting the considered space with prior knowledge. In contrast, Vnn explores similar tasks. This guides exploration to states and actions that prove useful, which restricts the explored space and overcomes relative overgeneralization. To the best of our knowledge, the only other work that explores the task space is Leibo al. (2019): they use the evolution of competing agents harder and harder tasks. Collaborative agents cannot compete against each other, though, and their approach does therefore not affect relative overgeneralization.
exploration between agents by shared latent variables, whereas[Jaques
auto-curriculum of
Successor Features Most of the work on SFs have been focused on single-agent settings (Dayan 1993 Kulkarni et al. 2016 Lehnert et al.) 2017 Zhu et al.) 2017 Barreto et al. 2017 2018 Borsa ct al. 2018 Lehnert & Littman 2019 Lee et al. 2019] Hansen et al.] 2019) for transfer learning and zero-shot generalization across tasks with different reward functions. Gupta et al. (2019) uses single-agent SFs in a transition transition-independdee independent multi-agen setting to estimate the probability of events.
CONCLUSION
This paper presents novel multi-agent universal successor features (MAUSFs) decomposed as local agent-specific SFs, which enables decentralized version of the GPI to maximize over a combinato- rial space of agent policies, making MAUSFs a perfect fit for MARL. We then propose Une VEn, which leverages the generalization power of MAUSFs to perform action-selection based on sim- pler related tasks to address the issue of sub-optimality of target task's 's monotonic joint-action value function in current SOTA methods. Our experiments show that Vn significantly outperforms VDN, QMIX and other state-of-the-an aalue-based MARL methods on nonmonotonic tasks by a substantial margin.

---

Under review as a conference paper at ICLR 2021
REFERENCES
André Barreto, Will Dabney, Rémi Munos, Jonathan J Hunt, Tom Schaul, Hado van Hasselt, and David Silver. Successor features for transfer in reinforcement learning. In Advances in neural information processing systems, pp. 4055-4065, 2017.
Andre Barreto, Diana Borsa, John Quan, Tom Schaul, David Silver, Matteo Hessel, Daniel Mankowitz, Augustin Zidek, and Remi Munos. Transfer in deep reinforcement learning using successor features and generalised policy improvement. In International Conference on Machine Learning, pp- 501-510. PMLR, 2018.
André Barreto, Shaobo Hou, Diana Borsa, David Silver, and Doina Precup. Fast reinforcement learning with generalized policy updates. Proceedings of the National Acudemy of Sciences, 2020.
Marc G. Bellemare, Sriram Srinivasan, Georg Ostrovski, Tom Schaul, David Saxton, and Rémi Munos. Unifying count-based exploration and intrinsic motivation. Advances in Neural Infor- mation Processing Systems (NIPS 29, pp. 1471-1479, 2016.
Wendelin Böhmer, Tabish Rashid, and Shimon Whiteson. Exploration with unreliable intrinsic reward in multi-agent reinforcement learning. CoRR, abs/1906.02133 2019. URL http:
//arxiv. org http://b//99.... 02138 Presented at the ICML Exploration in Reinforcement
Learning workshop.
Wendelin Böhmer, Vitaly Kurin, and Shimon Whiteson. Deep coordination graphs In Proceedings of Machine Learning and Systems (ICML), pp. 2611-2622, 2020. URL https:///aaat
org/ abs / 1910. 00091
Diana Borsa, André Barreto, John Quan, Daniel Mankowitz, Rémi Munos, Hado Hasselt, David Silver, and Tom Schaul. Universal successor features approximators. arXiv preprint 1oXiv:/812.07022 2018.
Yuri Burda, Harri Edwards, Deepak Pathak, Amos Storkey, Trevor Darrell, and Alexei A. Efros. Large-scale study of curiosity-driven learning. In International Conference on Learning Repre- sentations (ICLR), 2019.
Junyoung Chung. Caglar Gulcehre, KyungHyun Cho, and Yoshua Bengio. Empirical evaluation of gated recurrent neural networks on sequence modeling. arXiv preprint arXiv:1412.3555, 2014.
Peter Dayan. Improving generalization for temporal difference learning: The successor representa- tion. Neural Computation, 5(4):613-62) 624, 1993.
Jakob N Foerster, Gregory Farquhar, Triantafyllos Afouras, Nantas Nardelli, and Shimon White- son. Counterfactual multi-agent policy gradients. In Thirty-second AAAI conference artificial intelligence, 2018.
Meire Fortunato, Mohammad Gheshlaghi Azar, Bilal Piot, Jacob Menick, Matteo Hessel, Ian Os- band, Alex Graves, Volodymyr Mnih, Remi Munos, Demis Hassabis, Olivier Pictquin. Charles Blundell, and Shane Legg. Noisy networks for exploration. In International Conference on Learning Representations (ICLR), 2018. URL ЕYWHCPKAW
Yarin Gal, Jiri Hron, and Alex Kendall. Concrete dropout. In Advances Neural Information Processing Systems (NIPS), pp. 3584-3593, 2017.
Carlos Guestrin, Michail Lagoudakis, and Ronald Parr. Coordinated reinforcement learning. In ICML, volume pp. 227-234. Citeseer, 2002.
Tarun Gupta, Akshat Kumar, and Praveen Paruchuri. Successor features based multi-agent for event-based decentralized mdps. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 6054-6061, 2019.
Steven Hansen, Will Dabney, Andre Barreto, Tom Van de Wiele, David Warde-Farles and Volodymyr Mnih. Fast task inference with variational intrinsic successor features. arXiv preprint arXiv: 05030, 2019.
10

---

Under review as a conference paper at ICLR 2021
Natasha Jaques, Angeliki Lazaridou, Edward Hughes, Çaglar Gülgehre, Pedro A. Ortega, DJ Strouse, Joel Z. Leibo, and Nando de Freitas. Intrinsic social motivation via causal influ- ence in multi-agent RL. CoRR, abs/1810.086477, 2018. URL ptttps://axii..oo org/abs/ /bs/
1810. 08647
Landon Kraemer and Bikramjji Banerjee. Multi-agent reinforcement learning a rehearsal for decentralized planning. Neurocomputiing, 190:82-94, 2016.
Tejas D Kulkarmi, Ardavan Saeedi, Simanta Gautam, and Samuel J Gershman. Deep successor reinforcement learning. arXiv preprint arXiv:1606.023300 2016.
Donghun Lee, Srivatsan Srinivasan, and Finale Doshi-Velez. Truly batch apprenticeship learning with deep successor features. arXiv preprini arXiv: /0077 2019.
10077,
Lucas Lehnert and Michael L Littman. Successor features support model-based and model-free reinforcement learning. CoRR abs/1901. 2019.
Lucas Lehnert, Stefanie Tellex, and Michael L Littman. Advantages and limitations of using suc- cessor features for transfer in reinforcement learning. arXiv preprint arXiv: AxXiv:700.000000 2017.
Joel Z. Leibo, Edward Hughes, Marc Lanctot, and Thore Graepel. Autocurricula and the emergence of innovation from social interaction: manifesto for multi-agent intelligence research. CoRR, abs/1903.00742, 2019. URLbttzp /ttp:://arree //trxvaaavvvv//aa org/ abs 1901. 1903.00742
Long-Ji Self-improving reactive agents based on reinforcement learning, planning and teaching. Machine Learning, 8(3):293-321, 1992.
Anuj Mahajan, Tabish Rashid, Mikayel Samvelyan, and Shimon Whiteson. Maven: Multi-agent variational exploration. In Advances in Neural Information Processing Systems, pp. 7613-7624,
2019.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare G Belle- mare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski. et al. Human-level control through deep reinforcement learning, Nature, 518(7540):529-533 2015.
Brendan O' o'Donoghue, Ian Osband, Rémi Munos, and Volodymyr Mnih. The uncertainty Bell- man equation and exploration. In Proceedings of the 35th International Conference on Machine Learning (ICML), pp. 3836-3845, 2018. URL WRRLhttp:
ml ml..press/v8C/
o donoghuueee50 18a. html
Frans A Olichoek, Christopher Amato, et al. A concise introduction to decentralized POMDPs, volume 1. Springer, 2016.
Afshin OroojlooyJadid and Davood Hajinezhad. A review of cooperative multi-agent deep rein- forcement learning. arXiv preprint 1rXiv:/908.0330 03963, 2019.
Ian Oshand, Benjamin Van Roy, and Zheng Wen. Generalization and exploration via randomized value functions. In Proceedings the 33rd International Conference International Conference on Machine Learning (ICML), pp. 2377-2386, 2016.
Liviu Panait, Sean Luke, and R Paul Wiegand. Biasing cocvolutionary search for optimal multiagent behaviors. IEEE Transactions on Evolutionary Computation, (0(6):629-444 2006.
Deepak Pathak, Pulkit Agrawal, Alexei A. Efros, and Trevor Darrell. Curiosity driven exploration by self-supervised prediction. In Proceedings of the 34th International Conference on Machine Learning (ICMI), 2017.
Tabish Rashid, Gregory Farquhar, Bei Peng, and Shimon Whiteson. Weighted qmix: Expanding monotonic value function factorisation. arXiv preprint arXiv:2006.10800, 2020a.
Tabish Rashid, Mikayel Samvelyan. Christian Schroeder De Witt, Gregory Farquhar, Jakob Foerster, and Shimon Whiteson. Monotonic value function factorisation for deep multi multi-agent reinforcement learning. arXiv preprint arXiv:2003.08839 2020b.

---

Under review as a conference paper at ICLR 2021
Melrose Roderick, Christopher Grimm, and Stefanie Tellex. Deep abstract Q-networks. In Pro- ceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS), pp. 131-138, 2018.
Mikayel Samvelyan, Tabish Rashid, Christian Schroeder de Witt, Gregory Farquhar, Nantas Nardelli, Tim GJ Rudner, Chia-Man Hung, Philip HS Torr, Jakob Foerster, and Shimon Whiteson. The starcraft multi-agent challenge. arXiv preprint 1XXi:19022000433 2019.
Tom Schaul, Daniel Horgan, Karol Gregor, and David Silver. Universal value function approxima- tors. In International conference machine learning, pp. 1312-1320, 2015.
Kyunghwan Son, Daewoo Kim, Wan Ju Kang, David Earl Hostallero, and Yung Yi. Qtran: Learn- ing to factorize with transformation for cooperative multi-agent reinforcement learning. arXiv preprint arxiv:1905.
2019.
Kyunghwan Son, Sungsoo Ahn, Roben Delos Reyes, Jinwoo Shin, and Yung Yi. Qtran++: Improved value transformation for cooperative multi-agent reinforcement learning, 2020.
Peter Sunehag, Guy Lever, Audrunas Gruslys, Wojciech Marian Czarnecki, Vinicius Zambaldi, Max Jaderberg, Mare Lanctot, Nicolas Sonnerat, Joel Leibo, Karl Tuyls, et al. Valle-decompoosition networks for cooperative multi-agent learning. arXiv preprint arXiv:1706.05290 2017.
Ming Tan. Multi-agent reinforcement learning: Independent cooperative agents. In Proceedings of the tenth international conference on machine learning, pp- 330-337, 1993.
Haoran Tang, Rein Houthooft, Davis Foote, Adam Stooke, OpenAl Xi Chen, Yan Duan, John Schul- man, Filip DeTurek, and Pieter Abbeel. #Exploration: study of count-based exploration for deep reinforcement learning. In Advances in Neural Information Processing Systems (NIPS) 30, pp. 2753-2762. 2017.
Hado van Hasselt, Arthur Guez, and David Silver. Deep reinforcement learning with double q- learning. In Proceedings of the 13th AAAI Conference Artificial Intelligence, pp. 2016. URL/attps: http///axvivvv.////v///..//...va org pttpppp/////// 064.1.....6666..... pd
Jianhao Wang, Zhizhou Ren, Terry Liu, Yang Yu, and Chongjie Zhang. Qplex: Duplex dueling multi-agent geearnnngg arXiv preprint arXiv:2008.00 01062, 2020a.
Tonghan Wang. Jianhao Wang, Yi Wu, and Chongjie Zhang. Influence-based multi-agent ex- ploration. In International Conference on Learning Representations, 2020b. URL https:
//openreview. wwtp:neet//oodddeeeeeoooo.
(to.ep/rr.....eee/fooomo...oooo. B
Ziyu Wang, Tom Schaul, Matteo Hessel, Hado Hasselt, Mare Lanctot, and Nando Freitas. Ducling network architectures for deep reinforcement learning. In International conference on machine learning, pp. 1995-2003, 2016.
Ermo Wei, Drew Wicke, David Freelan, and Sean Luke. Multiagent soft q-learning. arXiv preprint 0987878 2018.
Stephan Zheng and Yisong Yue. Structured exploration via hierarchical variational policy networks, 2018.
Yuke Zhu, Daniel Gordon, Eric Kolve, Dieter Fox. Li Fei-Fei, Abhinav Gupta, Roozbeh Mottaghi, and Ali Farhadi. Visual semantic planning using deep successor representations. In Proceedings of the IEEE international conference computer vision, pp. 483-492, 2017.
12

---

Under review as a conference paper at ICLR 2021
A TRAINING ALGORITHM
Algorithm ! presents the training of MAUSFs with Une Our method is able to learn on all tasks (target and sampled 2) simultaneously in sample efficient manner using the same feature Φ = (8,, u,) due to the linearly decomposed reward function (Equation
Algorithm Training MAUSFs with Une
Require: 6, 0z, B target task un set of agents A, standard deviation
1: procedure TRAIN:
2: Initialize the local-agent SF network 2/5 (r" u², 22 and replay buffer M
3: for fixed number of epochs do Og RESETENV(
4:
((w,oL))
0, foftaEd
5:
t t= 0; M NEWEPISODE 0o)
6:
while not terminated do Bernoulli(e)=1 then u + Uniform(24) else u4 <- UNEVEN(TI, v) (0++1 Φ2) t ENVSTEP(U,)
7:
8:
9:
10:
M <- ADDTRANSITION (MOIONSSTIOONMMMMMM.MMMMMM Oc, t ++++1
11:
12:
L 0: B+ SAMPLEMINIBATCH(M
foreach (Te, uhs Φr, Te+1, B do foreach E u (w) do u1 + { arg max ( u wEll
14:
15:
16:
C L || + v
tho uc, 0)
17:
- OPTIMIZE(O. VoL)
+ (1 8)0 300
19:
procedure UNEVEN(T,.2)) v): if Bernoullíaa)
20:
Scheme is Target then C2 - (w)
21:
22:
else
23:
if Scheme is Uniform then
24:
C2 - Uniform(v)
25:
else if Scheme is Greedy then
C2 < [w]
27:
if Use Cii.GGPIPPPccc is True then
28:
Ci / {w}
29:
U₁ + {ui = arg max max max 86"h (TT 2; ( kFaEA
30:
else
wEll kECa sEC,
31:
Ut {uf arg max max (T(, u, kr Tk)aad
return Ut
well kEC,
B EXPERIMENTAL DOMAIN DETAILS AND ANALYSIS
We consider a complicated partially observable predator-pree (PP) task an 10 10 grid involving eight agents (predators) and three preys that is designed to test coordination between agents, as each prey needs a simultaneous capture action by at least three surrounding agents to be captured. Each agent can take 6 actions i.e. move in one of the 4 directions (Up, Left, Down, Right), remain still (no-op), or try to catch (capture) any adjacent prey. The prey moves around in the grid with a probability of 0.7 and remains still at its position with probability 0.3. Impossible actions for both agents and prey are marked unavailable, for eg. moving into an occupied cell or trying to take a capture action with adjacent prey.
13

---

Under review as a conference paper at ICLR 2021
Al Al-Capture A2-Capture A2-Other
Al-Other
A2- A2-Capture
A2-Other
A3-Capture
+1
-
A3-Capture A3-Other
P
A3-Other
P
P
-P
0
Table 1: Joint-Reward function of three agents surrounding prey. The first table indicates joint- rewards when Agent takes capture action and second table indicates joint-rewards when Agent takes any other action. Notice that there numerous joint actions leading to penalty p.
If either single or a pair of agents take capture action on an adjacent prey, a negative reward of magnitude is given. If three or more agents take the capture action on an adjacent prey, it leads to successful capture of that prey and yield positive reward of +1. The maximum possible reward for capturing all preys is therefore +3. Each agent observes a 5 x 5 grid centered around its position which contains information showing other agents and preys relative to its position. An episode ends if all preys have been captured or after 800 time steps. This task is similar to one proposed by Böhmer et al. (2020); [Snn et al. (219)), but significantly more complex in terms of the coordination required amongst agents as agents need to coordinate simultancously capture the preys. We now prove Proposition which states that:
Proposition. For, the predator-prey game defined above, the optimal joint action reward function for any group of 2 < k < n predator agents surrounding prey is nommonotonic (as defined by Mahajan al. 2019) iff p >
Proof. Without loss of generality, we assume a single prey surrounded by three agents (Ai, A2, Aa) in the environment. The joint reward function for this group of three agents is defined Table [T]
For the case p 0 the proposition monotonicity (Mahajan et al. 2019). For any < k v n agents attempting to catch a prey in state s, we fix the actions of any le agents be "other" indicating either of up, down, left, right, and noop actions and represent it with 8-3 Next we consider the rewards r for two cases:
be casily verified using the definition of non-
If we fix the action of any two of the remaining three agents "other" represented as u², the action of the remaining agent becomes u² = arg max r(s, (u, ui (2) "other".
If fix the u² be "capture", have ui arg max r8,, (u, u² u x3)) "capture".
Thus the best action for agent A₁ in state depends the actions taken by the other agents and the rewards R(s) are non-monotonic. Finally for the equivalence, we note that for the case = 0 we have that default action of "capture" is always optimal for any group of ls predators surrounding the prey. Thus the rewards are monotonic as the best action for any agent is independent of the rest.
C IMPLEMENTATION DETAILS
C.1 HYPER PARAMETERS
All algorithms are implemented in the PyMARL framework (Samvelyan et al., 2019). All our experiments use e-greedy scheme where decayed from
0.05 over 250k time steps. All our tasks use a discount factor of ς = 0.99. We freeze the trained policy every 30k timesteps and run 20 evaluation episodes with for all experiments. We use a target network similar to Mnih et al. (205)) with "soft" target updates, rather than directly copying the weights: 0- f- 8 0
0. We use learning rate of 0.0005 with soft target updates
3) * 0=, where 0 are the current network parameters. We use 3 = 0..05 for all experiments. This means that the target values are constrained to change slowly, greatly improving the stability of learning. All algorithms were trained with RMSprop optimizer by one gradient step loss computed on batch of 32 episodes sampled from a replay buffer containing last 1000 episodes. We also used gradient clipping to restrict the norm of the gradient to be < 10.
14

---

Under review as a conference paper at ICLR 2021
0.004
= 0.008
Hean Test Raturn
Gready-GPi
Target-GPi
Refform-GPP
Greedy-Gnn
Terget-ore
unrifom-do GPI
0.0
0.0
Figure 8: Additional Ablation results: Comparison between different action selection of UneVEn for (0.004, 0.008}.
Zero-Shot Generalization
2
244
2,48
1
2
1,2
Mean Test Return
1..44 -X-F -S1.0
9.33
SU.E
-27.28
C.08 -3.L8
407
4.00
-7.88
06.33
-2
-6
UneVEn-Greedy-GFE
WQMIX MAVEN
VDN
UneVEn-Uniform-ee
-10
p 0.2
= 0.3
p 0.5
p 1.0
Figure 9: Additional Zero-shot generalization results for E 00.2, 1.03.
The probability a of action selection based on target task in UneVEn with uniform and greedy action selection schemes increases from 0.3 to 1.0 over 250k time steps. For sampling related tasks using normal distribution, we use N(w, Lla centered around target task w with a e {0.1, 0.2). At the beginning of each episode, we sample related tasks, therefore |v| = 6.
C.2 NN ARCHITECTRRE
Each agent's local observation of concatenated with agent's last action wf-1: and then passed through a fully-connected (FC) layers of 128 neurons, followed by ReLU activation, a GRU (Chung al. 2014), and another FC of the same dimensionality summary for the agent. Each agent's ' task vector E U { is passed through a FC layer of 128 neurons followed by ReLU activation to generate an internal task embedding. The history and task embedding are concatenated together and passed through two hidden FC-256 layers and ReLU activations generate the outputs for each action. For methods with non- non-linear mixing such as QMIX (Rashid et al. 2020b), WQMIX (Rashid et al. (020a), and MAVEN (Mahajan et al. (019). we adopt same hypernetworks from the original paper and test with either a single or double hypernet layers of dim 64 utilizing ELU non-lincarity. For all bascline methods, shared publicly by the corresponding authors on Github.
generate action-observation history
the code
D ADDITIONAL RESULTS
Figure 8 presents additional ablation results for comparison between UneVEn with different ac- tion selection schemes for p (0.004, 0.008). Figure presents additional zero-shot generaliza- tion results for policies trained on target task with penalty p 0.004 tested on tasks with penalty p E {0.2, 0.3, 0.5, 1.0}. For UneVEn- "VEEn-Grredy-GPP we can observe that the average number of mis- coordinated capture attempts per episode actually drops with p and converges around 1.5, i.e. for return Ry, average mistakes per episode is 3-R, (2.3,2.1, 1.5, 1.6) for {0.2, 0.3, 0.5, 1.0).
15

---

Under review as a conference paper at ICLR 2021
times
X
x
1
1
O
1
O
0
0
1
1
4
O
O
1
O
X
X
8 times
initial state
stestep matrix game from Mahajan et al. (2019) for 10. The red cross means that selecting that joint action will lead to termination the episode.
Figure 10:
E m-STEP MATRIX GAMES
Figure 10 shows the m-step matrix game for m 10 from Mahajan et al. (2019), where there are 2 intermediate steps, and selecting joint-action with zero reward leads to termination of the episode.
16


Reviews:
[{"review_id": "zCJSsZWA7NV", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Some popular methods like VDN and QMIX focus on the monotonic factorization of joint-action value function, which is not realistic in non-monotonic cases when the agent’s best action depends on other agents’ actions. This phenomenon is common. For example, in the prisoner’s dilemma the value function can be monotonically decreasing in each of the agent’s local value function. One of the effect this paper focuses on is that the monotonically factorization lacks the representational capacity to distinguish the values of coordinated and uncoordinated joint actions during exploration. This effect is well explained in the predator-prey game example, where both VDN and QMIX have undesired performance. \n\nRecent work like QTRAN and WQMIX tried to address the problem of inefficient exploration caused by monotonic factorization. However, these approaches still rely on inefficient-greedy exploration which may fail on harder tasks e.g., again, the predator-prey task above with higher value of p.\n\nThis paper applies universal successor features to the multi-agent setting (Multi-Agent Universal Successor Features MAUSFs). Decentralized agent-specific SFs with VDN enables agents to compute decentralized greedy policies and to perform decentralized local GP. The two components have some good synergy and improves VDN to some extent. The propose Universal Value Exploration (UneVEn) can solve tasks with nonmonotonic values. Both the combination of SF and VDN and the UneVEn algorithm are very intuitive and are easy to understand and implement.\n\nHowever, the strength of the results are moderate. As it is very natural to combine the two it suffices to figure out how strong the synergy is between. This is not observed either through theoretical insights or experimental studies. To be specific, the experiments study only the game of predator-prey and do not yet demonstrate the algorithm’s generalization power beyond this motivating task. It should outperform existing approaches on a wider range of tasks where the monotonicity does not hold, and be at least competitive on tasks where such an assumption hold, to be valuable. The experiment on Zero-shot generalization is interesting, but SF along should be able to present such an effect of transfer learning (generalization). The paper needs to show how the synergy between SF and VDN is really like in the task of transfer.\n\nPro\n \t1. This paper keeps up with the frontier of MARL. It discusses a lot of algorithms proposed recently and provides a detailed background knowledge.\n\n2. It clearly stated the current research gap in value function factorization. \n \t\nWeak points \n \t1. This paper might not fill the research gap it mentioned very well. For example, in the introduction part, it says the shortages of VDN and QMIX is that they are restricted by monotonic property. However, it states in the UneVEn section that, \"the basic idea is some of the related tasks can be efficiently learned using a monotonic joint-action value function. \" Does it mean that the implementation of UneVEn still relies on monotonic value function? \n \t\n2. The author can elaborate more on the experiments from an intuitive view, rather than just stating the experiment data.\n \tFor example, as the experiment shows, the UneVEn only outperforms as the penalty parameter p get larger and larger. What's the reason behind it? How does UneVEn overcome the \"curse\" of suboptimal stuck in VDN and QMIX? \n\n3. More experiments on general tasks should be provided.", "extra_scores": {}, "extra_text": {}}, {"review_id": "kPAK6FEnfJw", "reviewer": "AnonReviewer3", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper employs the linear value factorization proposed by VDN and extends universal successor features with GPI to multi-agent reinforcement learning. It also proposes an exploration method, called universal value exploration, that biases an agent’s action selection by utilizing related tasks. Empirical evaluation demonstrates its outperformance over baselines in predator-prey tasks. \n\nHowever, I have some major concerns about this paper.  First, the motivation of this paper is confusing, that is, the monotonic restriction leads to inefficient exploration. Exploration and the expressiveness of value factorization do not have a causal relation. Some exploration strategies can allow VDN and QMIX to learn the optimal strategy even with non-monotonic returns. One of such trivial exploration policies is the optimal (or nearly optimal) policy.  \n\nThe proposed MAUSFs approach looks like a simple extension of single-agent successor features to multi-agent settings by using linear value factorization.  Are there challenges for such an extension? \n\nI don’t think the proposed UNEVEN exploration method can address the relative overgeneralization pathology. The relative overgeneralization pathology is caused by the limited function class of some value factorization methods. QTRAN and QPLEX can potentially address this issue, but they may not perform well in some tasks that require more efficient exploration.  \n\nI don’t think it is fair to compare UNEVEN with most of the baselines in this paper. It is because UNEVEN uses the linear parameterized representation of reward functions that allows generating related tasks. In contrast, some baselines do not aim to address the exploration problem or do not take additional information. \n\nThe experimental evaluation can be improved. For example, it can include more complex settings, like SMAC.", "extra_scores": {}, "extra_text": {}}, {"review_id": "iTFRcZ7clFW", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "##########################################################################\nSummary:\n\nThis paper studies the problem setting of cooperative multi-agent RL (coop-MARL) under centralized training with decentralized execution (CTDE). Additionally, it assumes that the reward function is known and is represented as a weighted linear combination of a basis function.  \nThey consider Q-learning with value-decomposition as the basis for tackling such problems and improve upon SOTA methods for coop-MARL in the domain of predator-prey (PP). Specifically, they claim to improve upon monotonic value-decomposition methods such as VDN and QMIX by better addressing the issue of relative overgeneralization which stems from their monotonicity constraint in representing the joint-action value function. This paper has a similar objective as Weighted QMIX, but it achieves it through implicit weighting by learning over a set of related tasks (reward function weights).    \nTheir approach is to extend Value-Decomposition Networks (VDN) by combining it with a multi-agent version of USFs (Successor Features + reward-function-based Universal Value Functions), called MAUSFs. Then, they use a related-task sampler during exploration to sample simpler tasks and through this, they claim that more importance is placed on better joint actions implicitly.   \n\n##########################################################################\nReasons for score:\n\nOverall, I think this is, in general, a sound paper and so would like to see it accepted. As a paper to inspire and give insights on issues in coop-MARL through a creative approach, I like this paper. However, regarding the general applicability and its practical usefulness, I'm not fully convinced yet. Additionally, I have some other concerns which, hopefully, the authors can address during the rebuttal period. \n\n##########################################################################\nPros:\n\n- The approach is innovative.\n\n- The experiments are targeted and illustrative. The zero-generalization experiment is also useful.\n\n- Paper is well-written and covers the literature appropriately.   \n\n##########################################################################\nCons:\n\nPlease see my questions below.\n\n##########################################################################\nQuestions during the rebuttal period:\n\n1) How can we ensure pi_z is optimal on task z? Isn't the optimality of pi_z on task z based on which the SF is learned a necessary condition for the GPI update to apply?\n\n2) I'm not fully convinced how in general this method can be expected to improve regarding the issue of relative overgeneralization? How do we know that these related tasks would bias the monotonic approximation towards \"more important\" joint actions? Is there a guarantee in the limit of tasks sampled by some distribution D? \n\n3) I have some concerns regarding the general applicability of this approach. To the best of my understanding, this work is limited to domains where the reward function is known and represented as a linear combination of some basis function. To me, this seems like a very challenging issue to overcome as breaking down the reward function based on experienced reward signals is perhaps as hard as learning the optimal action-value function (loosely speaking). \nSo can this approach really lead to more generic extensions that would work on unknown and general reward functions? \n\n4) Why does VDN's gap w.r.t. UneVEn narrows down (instead of widening) in p=0.004 (nonmonotonic) vs. p=0 (monotonic)?\n\n5) Why does QMIX perform so much worse than VDN in p=0.004 (in fact, on all tasks in Figures 2 & 3 this is the case)? Shouldn't QMIX's ability to represent a larger class of decompositions improve performance over VDN?\n\n##########################################################################\nMinor comments:\n\n- Section 1, paragraph 3: \"QTRAN (Son et al., 2019) and WQMIX (Rashid et al., 2020a) addresses...\" -> address\n\n- Remove the first comma in Proposition 1: \"For, the predator-prey game defined above,...\"\n\n- I think \\pi*_z should be used to indicate the optimal policy on task z is meant.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "fdJTj3pKETt", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper develops and evaluates an algorithm for decision making in the CTDE MARL setting (centralized training and decentralized execution for multiagent reinforcement learning). That is, the concern is how to use closely supervised training to produce agents that can work independently toward a common goal. The problem is formalized in the DEC-POMDP (decentralized partially observable Markov decision process) setting.\n\nThe proposed solution uses elements of several recent and promising approaches including value decomposition networks, QMIX (a nonlinear monotonic combination of individual utility functions), linear reward functions, universal value functions, successor features, generalized policy improvement. The novel idea is combining these ideas to create multi-agent universal successor features.\n\nThe power of the resulting algorithm was demonstrated in a set of predator-prey games with increased difficulty of learning to coordinate due to an increasing penalty value for accidental miscoordination. It was shown that other methods for this problem were not able to handle learning in the setting of high costs for coordination, but the proposed algorithm could.\n\nThe paper is quite good for what it claims to do. But, my impression is that the contribution is not very large. Specifically, the main demonstration was (significantly) improved performance on a predator-prey task. However, I am skeptical that these results will generalize  to other domains---these kinds of problems are quite hard and it's not clear if ANY algorithm would be expected to solve a diverse collection of real-world challenges. In the context of what the paper was trying to do, additional domains (3 distinct ones, say?) would go a long way toward characterizing the space of domains where this approach is appropriate.\n\nI guess I'm saying that this algorithm might be THE algorithm you'd want to use (it creatively combines a number of promising component ideas), but the paper didn't provide an argument for why the reader should be convinced that the positive results generalize.\n\nSome detailed comments:\n\n\"We now propose two novel action-selection schemes based on related tasks with probability 1-eps, and thereby implicitly weighting joint actions during learning.\" I'm afraid I wasn't able to parse this sentence. Reword?\n\npg. 6: Maybe putting the graphs on the same y-axis would aid in comparisons between settings (different values of p).\n\n\"However, both QMIX and VDN fail to learn on other three higher penalty target tasks\" -> \"However, both QMIX and VDN fail to learn on three other higher penalty target tasks\"?\n\n\"between different action selection\" -> \"between action-selection schemes\".\n\n\"learns a QMIX-factored joint-action value function along with an unrestricted centralized critic and propose\" -> \"learns a QMIX-factored joint-action value function along with an unrestricted centralized critic and proposes\"?", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper adapts the ideas around universal successor features for decentralised multi-agent environments, with a particular emphasis on deriving better exploration from them. Like most of the reviewers, I think this is indeed a promising research direction. Given the complexity of the endeavour however, it may take a few more steps until the empirical evidence can back up the authors' ambition: the reviewers' consensus on the current version of the paper is that it is not ready for publication yet.
Decision: Reject