LIGS: Learnable Intrinsic-Reward Generation Selection for Multi-Agent Learning 
Authors: David Henry Mguni
Taher Jafferjee
Jianhong Wang
Nicolas Perez-Nieves
Oliver Slumbers
Feifei Tong
Yang Li
Jiangcheng Zhu
Yaodong Yang
Jun Wang
Venue: ICLR 2022 Poster (2022)
Keywords: multi-agent
reinforcement learning
intrinsic rewards
exploration

Abstract: Efficient exploration is important for reinforcement learners (RL) to achieve high rewards. In multi-agent systems, coordinated exploration and behaviour is critical for agents to jointly achieve optimal outcomes. In this paper, we introduce a new general framework for improving coordination and performance of multi-agent reinforcement learners (MARL). Our framework, named Learnable Intrinsic-Reward Generation Selection algorithm (LIGS) introduces an adaptive learner, Generator that observes the agents and learns to construct intrinsic rewards online that coordinate the agents’ joint exploration and joint behaviour. Using a novel combination of reinforcement learning (RL) and switching controls, LIGS determines the best states to learn to add intrinsic rewards which leads to a highly efficient learning process. LIGS can subdivide complex tasks making them easier to solve and enables systems of RL agents to quickly solve environments with sparse rewards. LIGS can seamlessly adopt existing multi-agent RL algorithms and our theory shows that it ensures convergence to joint policies that deliver higher system performance. We demonstrate the superior performance of the LIGS framework in challenging tasks in Foraging and StarCraft II and show LIGS is capable of tackling tasks previously unsolvable by MARL methods.

Published as a conference paper at ICLR 2022
LIGS: LEARNABLE INTRINSIC-REWARE GENERATION SELECTION FOR MULTI-AGENT LEARNING
David M Taher Jafferjee' Jiannonng Wang?, Oliver Slumbers' Nicolas Perez-Nieves", Feifei Tong', Li Yang". Jiangcheng Zhu', Yaodong Yang', Jun Wang² 'Huawei Technologies, Imperial College London, *Shanghaitech University, *Institute for AI, Peking University & BIGAI, University College London
ABSTRACT
Efficient exploration is important for reinforcement learners to achieve high re- wards. In multi-agent systems, coordinated exploration and behaviour is critical for agents to jointly achieve optimal outcomes. In this paper, we introduce a new general framework for improving coordination and performance of multi-agent re- inforcement learners (MARL). Our framework, named Learnable Intrinsic-Rewane Generation Selection algorithm (LIGS) introduces an adaptive learner, Generator that observes the agents and learns to construct intrinsic rewards online that coordi- nate the agents' joint exploration and joint behaviour. Using a novel combination of MARL and switching controls, LIGS determines the best states to learn add intrinsic rewards which leads to a highly efficient learning process. LIGS can subdivide complex tasks making them easier to solve and enables systems of MARL agents to quickly solve environments with sparse rewards. LIGS can seamlessly adopt existing MARL algorithms and, theory shows that it ensures convergence to policies that deliver higher system performance. We demonstrate its superior performance challenging tasks in Foraging and StarCraft II.
INTRODUCTION
Cooperative multi-agent reinforcement learning (MARL) has emerged as a powerful tool to enable autonomous agents to solve various tasks such as autonomous driving (Zhou et al., 2020b), ride- sharing (Li et al., 2019), gaming AIs (Peng et al., 2017a), power networks (Wang al., 2021a; Qiu et al., 2021) and swarm intelligence (Mguni et al., 2018; 8; Yang et al., 2017). In multi-agent systems (MAS), maximising system performance often requires agents coordinate during exploration and learn coordinated joint actions. However, in many MAS, the reward signal provided by the environment is not sufficient guide the agents towards coordinated behaviour (Matignon al., 2012). Consequently, relying on solely the individual rewards received by the agents may not lead to optimal outcomes (Mguni et al., 2019). This problem is exacerbated by the fact that MAS can have many stable points some of which lead to arbitrarily bad outcomes (Roughgarden & Tardos, 2007).
As in single agent RL, in MARL inefficient exploration can dramatically decrease sample efficiency. In MAS, major challenge is how to overcome sample inefficiency from poorly coordinated explo- ration. Unlike single agent RL, in MARL, the collective of agents is typically required to coordinate its exploration to find their optimal joint policies'. A second issue is that in many MAS settings of interest, such as video games and physical tasks, rich informative signals of the agents' joint performance are not readily available (Hosu & Rebedea, 2016). For example, in StarCraft Microman- agement (Samvelyan et al., 2019), the sparse reward alone (win, lose) gives insufficient information to guide agents toward their optimal joint policy. Consequently. MARL requires large numbers of samples producing a great need for MARL methods that can solve such problems efficiently.
To aid coordinated learning, algorithms such QMIX (Rashid et al., 2018), MF-Q (Yang al., 2018), Q-DPP (Yang et al., 2020), COMA (Foerster et al., 2018) and SQDDPG (Wang et al., 2020c), so- called centralised critic and decentralised execution (CT-DE) methods use centralised critic whose
Correspondence to davidmguni @ hotmail.com.
Unlike single agent RI,, MARI exploration issues cannot be mitigated by adjusting exploration rates policy variances (Mahajan et al., 2019).

---

Published as a conference paper at ICLR 2022
role is to estimate the agents' expected returns. The critic makes use of all available information generated by the system. specifically the global state and the joint action (Peng et al., 2017b). To enable effective CT-DE, it is critical that the joint greedy action should be equivalent to the collection principle (Son et al., 2019). CT-DE methods are however, prone convergence to suboptimal joint policies (Wang et al., 2020a) and suffer from variance issues for gradient estimation (Kuba et al., 2021). Existing value factorisations, e.g. QMIX and VDN (Sunehag et al., 2017) cannot ensure an exact guarantee of IGM consistency (Wang et al., 2020b). Moreover, CT-DE methods such as QMIX require a monotonicity condition which is violated in scenarios where multiple agents must coordinate but are penalised if only a subset of them do so (see Exp. 2, Sec. 6.1).
of individual greedy actions of agents, which is called the IGM Sadividuull-Goobal---e
To tackle these issues, in this paper we introduce a new MARI. framework, LIGS that constructs intrinsic rewards online which guide MARL learners towards their optimal joint policy. LIGS involves an adaptive intrinsic reward agent, the Generator that selects intrinsic rewards add according to the history of visited states and the agents' joint actions. The Generator adaptively guides the agents' exploration and behaviour towards coordination and maximal joint performance. A pivotal feature of LIGS is the novel combination of RL and switching controls (Mguni, 2018) which enables it to determine the best set of states to learn to add intrinsic rewards while disregarding less useful states. This enables the Generator to quickly learn how set intrinsic rewards that guide the agents during their learning process. Moreover, the intrinsic rewards added by the Generator can significantly deviate from the environment rewards. This enables LIGS to both promote complex joint exploration patterns and decompose difficult tasks. Despite this flexibility, special features within LIGS ensure the underlying optimal policies are preserved so that the agents learn to solve the task hand.
Overall, LIGS has several advantages:
LIGS has the freedom to introduce rewards that vastly deviate from the environment rewards. With this, LIGS promotes coordinated exploration (i.e. visiting unplayed state-joint actions) among the agents enabling them to find joint policies that maximise the system rewards and generates intrinsic rewards to aid solving sparse reward MAS (see Experiment in Sec. 6.
LIGS selects which best states to add intrinsic rewards adaptively in response to the agents' be- haviour while the agents learn leading an efficient learning process (see Investigations in Sec. 6.1).
LIGS's intrinsic rewards preserve the agents' optimal joint policy and ensure that the total environ- ment return is (weakly) increased (see Sec. 5).
To enable the framework to perform successfully, we overcome several challenges: i) Firstly, con- structing intrinsic reward can change the underlying problem leading the agents solving irrelevant tasks (Mannion et al., 2017). We resolve this by endowing the intrinsic reward function with special form which both allows rich spread of intrinsic rewards while preserving the optimal policy. ii) Secondly, introducing intrinsic reward functions can worsen the agents' performance (Devlin & Kudenko, 2011) and doing so while training can lead to convergence issues. We prove LIGS leads to better performing policies and that LIGS's learning process converges and preserves the MARL learners' convergence properties. iii) Lastly, adding an agent Generator with its own goal leads to a Markov game (MG) with N + agents (Fudenberg & Tirole, 1991). Tractable methods for solving MGs are extremely rare with convergence only in special cases (Yang & Wang. 2020). Nevertheless, using special set of features in LIGS's s design, we prove LIGS converges to a solution in which it learns an intrinsic reward function that improves the agents' performance.
RELATED WORK
Reward shaping (Harutyunyan et al., 2015; Mguni al., 2021) is a technique which aims to alleviate the problem of sparse and uninformative rewards by supplementing the agent's 's reward with prefixed term F. Ng et al. (1999) it was established that adding a shaping reward function of the form F( 8t) = 70((()) $ )) Φ(st) preserves the optimal policy and in some cases can aid learning. RS has been extended to MAS (Devlin et al., 2011; Mannion et al., 2018; Devlin & Kudenko, 201 I; 2012; 2016; Sadeghlou et al., 2014) in which it is used to promote convergence to efficient social welfare outcomes. Poor choices of F in a MAS can slow the learning process and can induce convergence to poor system performance (Devlin & Kudenko, 2011). In MARL, the question of which shaping function to use remains unaddressed. Typically, RS algorithms rely on hand-crafted shaping reward functions that are constructed using domain knowledge, contrary the goal of
2

---

Published as a conference paper at ICLR 2022
autonomous learning (Devlin & Kudenko, 2011). As we later describe LIGS, which successfully learns an instrinsic reward function F, uses a similar form as PBRS however, F is now augmented to include the actions of another RL agent to learn the intrinsic rewards online. In Du et al. (2019) an approach towards learning intrinsic rewards is proposed in which a parameterised intrinsic reward is learned using a bilevel approach through centralised critic. In Wang et al. (2021b), a parameterised intrinsic reward is learned by corpus, then the trained intrinsic reward is frozen on parameters and used assist the training of single-agent policy for generating the dialogues. Loosely related are single-agent methods (Zheng et al., 2018; Dilokthanakul et al., 2019; Kulkarni et al., 2016; Pathak al., 2017) which, in general, introduce heuristic terms to generate intrinsic rewards.
Multi-agent exploration methods seek to promote coordinated exploration among MARL learners. Mahajan et al. (2019) proposed hybridisation of value and policy-based methods that uses mutual information to learn diverse set of behaviours between agents. Though this approach promotes coordinated exploration, it does not encourage exploration of novel states. Other approaches to promote exploration in MARL while assuming aspects of the environment are known in advance and agents can perform perfect communication between themselves (Viseras et al., 2016). Similarly, to promote coordinated exploration in partially observable settings, Pesce & Montana (2020) proposed end-to-end learning of a communication protocol through a memory device. In general, exploration- based methods provide no performance guarantees do they ensure the optimal policy. Moreover, many employ heuristics that naively reward exploration to unvisited states without consideration of the environment reward. This can lead to spurious objectives being maximised.
Within these categories, closest to our work is the intrinsic reward approach in Du et al. (2019). There, the agents' policies and intrinsic rewards are learned with a bilevel approach. In contrast, LIGS performs these operations concurrently leading to a fast and efficient procedure. A crucial point of distinction is that in LIGS, the intrinsic rewards are constructed by an RL agent (Generator) with its own reward function. Consequently, LIGS can generate complex patterns of intrinsic rewards, encourage joint exploration. Additionally, LIGS learns intrinsic rewards only at relevant states, this confers high computational efficiency. Lastly, unlike exploration-bssed methods e.g., Mahajan et al. (2019), LIGS ensures preservation of the agents' joint optimal policy for the task.
PRELIMINARIES
A fully cooperative MAS is modelled by decentralised- -arrrr Markov decision process (Dec-MDP) (Deng et al., 2021). A Dcc-MDP is an augmented MDP involving a set of N 2 2 agents denoted by A that independently decide actions to take which they do simultancously over many rounds. Formally, dec-MDP a tuple M = SW,S, (Ai) P. R, 7) where S is the finite set of states, AA; is an action set for agent E N and S x A + P(D) is the reward function that all agents jointly seek to maximise where D is a compact subset of IR and lastly, P S x A x S - [0, 1] is the probability function describing the system dynamics where A := N A Each agent i E A uses a Markov policy n. S x A₁ + [0, 1] to select its actions. At each time t O. the system is in state 8t E S and each agent i E A' takes an action of E Ai. The joint action a = (a),..., a.²) E A produces an immediate reward r; R(st, a.) for agent i E and influences the next-state transition which is chosen according to P. The goal of each agent is to maximise its expected returns = 7 R(ss, az)). where TI, is compact measured by its value function v" (s) = By EE
Markov policy space and -i denotes the tuple of agents excluding agent i.
Intrinsic rewards can strongly induce more efficient learning (and can promote convergence to higher performing policies) (Devlin & Kudenko, 2011). We tackle the problem of how to learn intrinsic rewards produced by function F that leads to the agents learning policies that jointly maximise the system performance (through coordinated learning). Determining this function is a significant challenge since poor choices can hinder learning and the concurrency of multiple learning processes presents potential convergence issues in a system already populated by multiple learners (Zinkevich et al., 2006). Additionally, we require that the method preserves the optimal joint policy.
4 THE LIGS FRAMEWORK
To tackle the challenges described above, we introduce Generator an adaptive agent with its own objective that determines the best intrinsic rewards to give to the agents each state. Using
3

---

Published as a conference paper at ICLR 2022
observations of the joint actions played by the N agents, the goal of the Generator is to construct intrinsic rewards to coordinate exploration and guide the agents towards learning joint policies that maximise their shared rewards. To do this, the Generator learns how to choose the values of an intrinsic reward function F at each state. Simultaneously. the N agents perform actions to maximise their rewards using their individual policies. The objective for each agent i {I,..., is given by:
by
E
Σ o' (R+
Fo) 80 8
where 0 is determined by the Generator using the policy x [0. and @ C R' is the Generator's action set. The intrinsic reward function is given by (*) = 0f - 05 where ff g is the action chosen by the Generator and of = 0, VI < 0. θ can be a set of integers {l...., .....,K), K}). Therefore, the Generator determines the output of p (which it does through its choice of 05). With this, the Generator constructs intrinsic rewards that are tailored for the specific setting.
LIGS freely adopts any MARL algorithm for the N agents (see Sec. 10 in the Supp. Material). The transition probability P: S x A x S + [0, 1] takes the state and only the actions of the N agents as inputs. Note that unlike reward-sin -haping methods e.g. (Ng et al., 1999), the function F now contains action terms 0 which are chosen by the Generator which enables the intrinsic reward function to be learned online. The presence of the action & term may spoil the policy invariance result in Ng et al. (1999). We however prove policy invariance result (Prop. 1) analogous to that in Ng et al. (1999) which shows LIGS preserves the optimal policy of MR. The Generator is an RI. agent whose objective takes into account the history of states and N agents' joint actions. The Generator's 's objective is:
x Σ [-0
(s) Cc
(s), ar) + L(s) su = V' E
where (20,,, a) = R(s, a) + FO, The objective encodes Generator's is agenda, namely to maximise the agents' expected return. Therefore, using its intrinsic rewards, the Generator seeks to guide the set of agents toward optimal joint trajectories (potentially away from suboptimal trajectories, c.f. Experiment 2) and enables the agents to learn faster (c.f. StarCraft experiments See. 6). Lastly, S x A + R rewards Generator when the agents jointly visit novel state- jute--oint--ccion tuples and tends to 0 as the tuples are revisited. We later prove that with this objective, the Generator's 's optimal policy (for constructing the intrinsic rewards) maximises the expected (extrinsic) return (Prop. 1).
Since the Generator has its own (distinct) objective, the resulting setup is an MG, 9 = (W x S,),S, (A:)iex, O, P, R2 R,,7) where the new elements are {c). the Generator agent, R7 = R+ 1=F the new team reward function which contains the intrinsic reward FO. R. : the one-step reward for the Generator (we give the details of this later).
R.
Switching Control Mechanism
So far the Generator's 's problem involves learning to construct intrinsic rewards at every state which can be computationally expensive. We now introduce an important feature which allows LIGS to learn the best intrinsic reward only in a subset of states in which intrinsic rewards are most useful. This is in contrast to the problem tackled by the N agents who must compute their optimal actions at all states. To achieve this, we now replace the Generator's policy space with form of policies known as switching controls. These policies enable Generator to decide at which states to learn the value of intrinsic rewards. This enables the Generator to learn quickly both where to add intrinsic rewards and the magnitudes that improve performance since the Generator's 's magnitude optimisations are performed only a subset of states. Crucially, with this the Generator can learn its policy rapidly enabling it to guide the agents toward coordination and higher performing policies while they train.
At each state, the Generator first makes a binary decision decide switch on its F for agent i e WV using a switch I, which takes values in (0, 1}. Crucially, now the Generator is tasked with learning how to construct the N agents' intrinsic rewards only at states that are important for guiding the agents to their joint optimal policy. Both the decision to activate the function F and its magnitudes is determined by the Generator. With this, the agent i E N objective becomes:
R+ FO. 1.)]
2 n.0 (8u, Io) = E Σ r
V(s0, Io) E x (0. 1),
(2)
4

---

Published as a conference paper at ICLR 2022
where [x+1 1 r.. which is the switch for F which is 0 or and hre times that switch takes place' for example if the switch is first turned
the state 85 then turned off at 87, then T = and 72 = 7 (we will shortly describe these in more detail). At any state, the decision to turn on is decided by (categorical) policy Be S + {0, 1} which acts according Generator's 's objective. In particular, first, the Generator makes an observation of the state 8N E S and the joint action and using ge- the Generator decides whether or not to activate the policy g to provide an intrinsic reward whose value is determined by 8 ~ g. With this it can be seen the sequence of times {Tk] is Th = inf([ > Tk-1 8 E S, (*+) = } so the switching times. {Tx, are rules that depend on the state. Therefore, by learning optimal ge. the Generator learns the useful states to switch on F.
To induce the Generator selectively choose when switch on the additional rewards, each switch activation incurs a fixed cost for the Generator. In this case, the objective for the Generator is:
L(st, az) ]
D0
00 (50, Io) Errgg
Rº (8:, a.)
8:22 121
-1 which is whenever t T2k-1 and otherwise imposes a cost for each switch activation. The cost has two effects: first, it reduces the computational complexity of the Generator's 's problem since the Generator now determines subregions of S it should learn the values of F. Second, ensures the information- gain from encouraging the agents to explore state- action tuples is sufficiently high to merit activating stream of intrinsic rewards. We set To = 0,
where the Kronecker- function 8'
8, = 0, Vk N (0T.+1..... 0-441-1 remain non-zero), 0% vk S 0 and denote by [(t) = It.
Discussion on Computational Aspect The switching controls mechanism results frame- work in which the problem facing the Generator has a markedly reduced decision space in comparison to the agent's problem (though the agents share the same experiences). Crucially, the Generator must compute optimal intrinsic rewards at only subset of states which are chosen by ge- Moreover, the decision space for the switching policy 9. is S (0. 1} i.e each state it makes a binary decision. Consequently, the learning process for de is much quicker than the agents' policies which must optimise over the deci- sion space |||||A] (choosing an action every state). This results in the Generator rapidly learning its op- timal policies (relative to the agent) in turn, enabling the Generator to guide the agents towards its optimal policy during its learning phase. Also, in our experiments, we chose the size of the action set for the Generator. θ to be singleton resulting in a decision space of size |8] {0, 1} for the entire problem facing the Generator. We later show that this choice leads to improved performance while removing the free parameter of the dimensionality of the Generator's 's action set.
20tt
Agurts
Agenta oolice
R
Aguds audie
Figure 1: Schematic of the LIGS framework.
Summary of Events
At a time Ê E 0, The N agents makes an observation of the state 8, E S.
2. The N agents perform joint action a (at (a....., aa") sampled from (n ..... N
The Generator makes an observation of s; and a, and draws samples from its polices (de.g).
4.
If (s:) = 0:
o Each agent E V receives reward r; R(se, a:) and the system transitions to the next state 8 and steps 1 3 are repeated.
If (sx))=11
F computed using s, and the Generator action 6 ~ g. o Each agent i N receives reward rı + F and the system transitions to $141- At time + if the intrinsic reward terminates then steps 3 are repeated or if the intrinsic reward has not terminated then step 5 is repeated.
More precisely, (nehaoo are stopping times (Øksendal, 2003).
5

---

Published as a conference paper at ICLR 2022
4.1 THE LEARNING PROCEDURE
In Sec. 5, we provide the convergence properties of the algorithm, and give the full code of the algorithm in Sec. 9 of the Appendix. The algorithm consists of the following procedures: the Gener- ator updates its policy that determines the values 0 at each state and the states to perform switch while the agents . learn their individual policies {TI..... TT J. In our implementation. we used proximal policy optimization (PPO) (Schulman et al., 2017) the learning algorithm for both the Generator's s intervention policy ge and Generator's policy g. For the N agents we used MAPPO (Yu et al., 2021). for the Generator L term we use' L(st. ax) == || - Al where h is a random initialised network which is the target network which is fixed and h is the prediction function that is consecutively updated during training. We constructed F using a fixed neural network f: _R + RT and one-hot encoding of the action of the Generator. Specifically, i(f)) a one-hot encoding of the action f picked by the Generator. Thus, F00 of 1) i(0f) y ((0 1). The action set of the Generator is {1} where g is an MLP Rd + R.. Extra details are in Sec. 9.
5 CONVERGENCE AND OPTIMALITY OF LIGS
We now show that LIGS converges and that the solution ensures higher performing agent policies. The addition of the Generator's 's RL process which modifies N agents' rewards during learning can produce convergence issues (Zinkevich et al., 2006). Also ensure the framework is useful, we must verify that the solution of G corresponds to solving the MDP, M.. To resolve these issues, we first study the stable point solutions of G. Unlike MDPs, the existence of a solution in Markov policies is not guaranteed for MGs (Blackwell & Ferguson, 1968) and is rarely computable (except for special cases such as team and zero-sum MGs (Shoham & Leyton-Bree -Brow, 2008)). MGs also often have multiple stable points that can be inefficient (Mguni et al., 2019); in 9 such stable points would lead to poor performing agent joint policy. We resolve these challenges with the following scheme:
M LIGS preserves the optimal solution of 2t.
[ The MG induced by LIGS has a stable point which is the convergence point of MARI..
[M LIGS yields team payoff that is (weakly) greater than that from solving Di directly.
[VV] LIGS converges to the solution with a linear function approximators.
In what follows, we denote by II XigA The results are built under Assumptions 1 7 (Sec. 15 of the Appendix) which are standard in RL and stochastic approximation theory. We now prove the result [I] which shows the solution to 27 is preserved under the influence of LIGS:
Proposition 1 The following statements hold: max t ( max v (s), Vs S, Vi E N, Vg where 0 (s) Ex Di RR.. Tell ii) The Generator's optimal policy maximises t. (8) E Ei R(s,, ax) for any s E S.
*E1l
Result (i) says that the agents' problem is preserved under the Generator's influence. Moreover the agents' (expected) total return is that from the environment (extrinsic rewards). Result (ii) establishes that the Generator's optimal policy induces it to maximise the agents' joint (extrinsic) total return. The result is proven by careful adaptation of the policy invariance result in Ng et al. (1999) to our MARL switching control setting where the intrinsic-reward not added all states. Building on Prop. 1, we deduce the following result:
Corollary 1 LIGS preserves the dec-MDP played by the agents. In particular, let (ft. 9) be a stable point policy profile of the MG induced by LIGS, G then के a solution to the dec-MDP, M.
Therefore, the introduction of the Generator does not alter the fundamentals of the problem. Our next task is to prove the existence of stable point of the MG induced by LIGS and show it is limit point of a sequence of Bellman operations. To do this we prove that a stable solution of g exists and that G has special property that permits its stable point to be found using dynamic programming. The following result establishes that the solution of the MG G, can be computed using RL methods:
"This is similar to random network distillation (Burda et al., 2018) however the input is over the space A x S. By stable point profile we mean a Markov perfect equilihrium (MPE) (Fudenherg & Tirole, 1991).

---

Published as a conference paper at ICLR 2022
Theorem Given function V S x A R, G has stable point given by lim TV
sup V*.0 0- = V* o' where (x", g) is a stable solution of 9 and T is the Bellman operator (c.f. (5)).
fETI
Theorem proves that the MG G (which the game that is induced when Generator plays with the N agents) has stable point which is the limit of dynamic programming method. In particular, it proves the that the stable point of G is the limit point of the sequence T VV..VV.......................... Crucially, (by Corollary 1) the limit point corresponds to the solution of the dec-MDP M. Theorem I is proven by firstly proving that G has dual representation as an MDP whose solution corresponds to the stable point of the MG. Theorem enables using distributed learning methods i.c. MARL to solve G. Moreover, Prop. 1 indicates by computing the stable point of & leads to a solution of Dt. These results combined prove [II]. Our next result characterises the Generator policy ge and the optimal times to activate F. The result yields a key aspect of our algorithm for executing the Generator activations of intrinsic rewards:
tackle the problem of finding the solution to g
Proposition 2 The policy ge is given by: ge(St; It) HMMT V* It). V(s,, It) x (0. (0,1), where v is the solution in Theorem I, M is the Generator's intervention operator (c.f. (4)) and H is the Heaviside function, moreover т inf T= V=.9).
In general, introducing intrinsic rewards or shaping rewards may undermine learning and worsen overall performance. We now prove that the LIGS framework introduces an intrinsic reward which yields better performance for the N agents compared to solving M directly (III)).
Theorem Each agent's expected return R whilst playing G is (weakly) higher than the expected return for M (without the Generator) i.e. (s, 2 n (s), vs E S, vi E N.
Theorem shows that the Generator's influence leads to an improvement in the system performance. Note that by Prop. I, Theorem 2 compares the environment (extrinsic) rewards accrued by the agents so that the presence of the Generator increases the total expected environment rewards. We complete our analysis by extending Theorem capture (linear) function approximators which proves [IV]. We first define projection IT by: IIA := arg min || A] for any function A. (e(T/)E)R)
Theorem LIGS converges to the stable point of G, moreover, given a set of linearly independent basis functions +- {&1..... 6p} with Φ& L2, Vk. LIGS converges to limit point r" R. which &br where 3A = R MaPPmaxMMM,... Moreover, r* satisfies: || Q' S (1 (2) 1/2 JITQ" Q*
the unique solution to [T((rr*)
The theorem establishes the convergence of LIGS stable point (of 9) with the use of linear function approximators. The second statement bounds the proximity of the convergence point by the smallest approximation error that can be achieved given the choice basis functions.
EXPERIMENTS
We performed a series of experiments on the Level-based Foraging environment (Papoudakis et al., 2020) to test if LIGS: Efficiently promotes joint exploration 2. Optimises convergence points by inducing coordination. 3. Handles sparse reward environments. In all tasks, we compared the performance of LIGS against MAPPO (Yu al., 2021), QMIX (Rashid al., 2018); intrinsic reward MARL algorithms LIIR (Du et al., 2019), LICA (Zhou et al., 2020a), and a leading MARL exploration algorithm MAVEN (Mahajan et al., 2019). We then compared LIGS against these baselines in StarCraft Micromanagement II (SMAC) (Samvelyan detailed suite of ablation studies (see Appendix) in which we demonstrated LIGS' flexibility to accommodate i) different MARL learners, ii) different L bonus terms for the Generator objective. We also demonstrated the necessity of the switching control component LIGS and LIGS' improved of exploration bonuses.
al., 2019). Lastly, we ran
7

---

Published as a conference paper at ICLR 2022
6.1 COOPERATIVE FORAGING TASKS
Experiment 1: Coordinated exploration. We tested our first claim that LIGS promotes coordi- nated exploration among agents. To investigate this, we used version of the level-based foraging environment (Papoudakis et al., 2020) as follows: there are n agents each with level a, Moreover, there are 3 apples with level K such that Σ 0; K. The only way to collect the reward is if all agents collectively enact the collect action when they are beside an apple. This is challenging joint-exploration problem since to obtain the reward, the agents must collectively explore joint actions across the state space (rapidly) to discover that simultancously executing collect near an apple produces rewards. To increase the difficulty, we added penalty for the agents failing to coordinate in collecting the apples. For example, if only one agent uses the collect action near an apple, gets a negative reward. This results in monotonic reward structure. The performance curves given in Fig. 2 which shows LIGS demonstrates superior performance over the baselines.
Optimal joint policies. We next tested our second claim that LIGS can promote convergence to joint policies that achieve higher system rewards. To do this, we constructed a challenging experiment in which the agents must avoid converging to suboptimal policies that deliver positive but low rewards. In this experiment, the grid is divided horizontally in three sections; top, middle and bottom. All grid locations in the top section give a small reward r/n n the agent visiting them where n is the number of tiles in the each section. The middle section does not give any rewards. The bottom section rewards the agents depending on their relative positions. If one agent is at the top and the other at the bottom, the agent at the bottom receives reward -r/n each time the other agent receives a reward. both agents are the bottom, then one of the tiles in this section will give a reward R, r/2 < R < both agents. The bottom section gives reward otherwise. The agents start in the middle section and as soon as they cross to one section they cannot return to the middle. As is shown in Fig. 2, LIGS learns to acquire rewards rapidly in comparison to the baselines with MAPPO requiring around 400k episodes to match the rewards produced by LIGS.
Experiment 2:
Experiment 3: Sparse rewards. We tested our claim that LIGS promote learning in MAS with sparse rewards. We simulate a sparse reward setting using a competitive game between two teams of agents. One team is controlled by LIGS while the other actions of the agents belonging the other team are determined by fixed policy. The goal is to collect the apple faster than the opposing team. Collecting the apple results in reward of I, and rewards are otherwise. This challenging sparse reward since informative reward signals occur only apple when the apple is collected. As is shown in Fig. both LIGS and MAPPO perform well on the sparse rewards environment, whilst the other baselines are all unable to learn any behaviour on this environment.
Investigations. We investigated the workings of the LIGS framework. We studied the locations where the Generator added intrinsic rewards in Experiments and 2. As shown in the heatmap visualisation in Fig. 3, for Experiment 2, we observe that the Generator learns to add intrinsic rewards that guide the agents towards the optimal reward (bottom right) and away from the suboptimal rewards at the top (where some other baselines converge). This supports our claim that LIGS learns to guide the agents towards jointly optimal policies. Also, as Fig. 3 shows, LIGS's s switching mechanism
Gevetirated Explerstion
Optinal Jont
Figure 2: Left. Coordinated Exploration. Centre. Optimal joint policies. Right. Sparse rewards.
8

---

Published as a conference paper at ICLR 2022
Coordinates
Shaper Activators
Figure 3: Left. Heatmap of Exp. showing where Generator adds rewards. Centre. Plot of distance to other agent when Generator activates rewards in Exp 1. Right. Corresponding heatmap for Exp. 2.
Sm wo. Sez
corester
OurE
0.0
MAPPO
3-
LICA
MANIN
2.0
0.9
3652 vs. 3662
MMM2
1.0
1.0
0.5
0.5
20.5-
20.5
20.4-
20.4
0.2-
0.2
0.0
0.0
Soaga 1.0
Figure 4: Median win rate over the course learning SMAC. LIGS outperforms the baselines all maps. LIIR, LICA, and MAVEN are generally not visible as their win rate is negligible.
means that the Generator only adds intrinsic rewards at the most useful locations for guiding the agents towards their target. For Experiment 1, Fig. 3 shows that the Generator learns to guide the agents towards the apple which delivers the high rewards. Fig. 3 (Right) demonstrates striking behaviour of the LIGS framework it only activates the intrinsic rewards around the apple when both agents are at most 2 cells away from the apple. Since the agents receive positive rewards only when they arrive the apple simultaneously, this ensures the agents are encouraged coordinate their arrival and receive the maximal rewards and avoids encouraging arrivals that lead to penalties.
6.2 LEARNING PERFORMANCE IN STARCRAFT MULTI-AGENT CHALLENGE
To ascertain LIGS is effective even complex environments, we ran it on on the following SMAC maps 5m vs. 6m (hard), 6h vs. 8z, Corridor, 3s5z vs 3s6z and MMM2 (super hard). These maps vary in a range of MARL attributes such as number of units to control, environment reward density, unit action sets, and (partial)-observabil)) 'Steps'. These curves are generated by computing the median win rate (vs the opponent) of the agent regular intervals during learning. We ran 3 seeds of each algorithm (further setup details are in the Supp. material Sec 14). LIGS outperforms the baselines in all maps. In 5m 6m and 6h vs. 8z, the baselines do not approach the performance of LIGS. Corridor MAPPO requires over an extra million steps to match LIGS. In 3s5z 3s6z and MMM2, LIGS still outperforms the baselines. In summary, LIGS shows performance gains over all baselines in SMAC maps which encompass diverse MAS attributes.
In Fig. 4, report our results showing 'Win Rate' vs
CONCLUSION
We introduced LIGS, novel framework for generating intrinsic rewards which significantly boosts performance of MARL algorithms. Central to LIGS is a powerful adaptive learning mechanism that generates intrinsic rewards according the task and the MARL learners' joint behaviour. Our experiments show LIGS induces superior performance in MARL algorithms in range of tasks.

---

Published as a conference paper at ICLR 2022
8 ACKNOWLEDGEMENTS
We would like to thank Matthew Taylor and Aivar Sootla for their helpful comments.
REFERENCES
Albert Benveniste, Michel Métivier, and Pierre Priouret. Adaptive algorithms and stochastic approxi- mations, volume 22. Springer Science & Business Media, 2012.
David Blackwell and Tom Ferguson. The big match. The Annals of Mathematical Statistics, 39(1): 159-163, 1968.
Yuri Burda, Harrison Edwards, Amos Storkey, and Oleg Klimov. Exploration by random network distillation. arXiv preprini arXiv: 12894, 2018.
Xiaotie Deng, Yuhao Li, David Henry Mguni, Jun Wang, and Yaodong Yang. the complex- ity of computing markov perfect equilibrium in general-sum stochastic games. arXiv preprint arXiv:2109.01795, 2021.
Sam Devlin and Daniel Kudenko. Theoretical considerations of potential -bsed reward shaping for multi-agent systems. In The 10th International Conference on Autonomous Agents and Multiagent Systems, pp- 225 232. ACM, 2011.
Sam Devlin and Daniel Kudenko. Plan-based reward shaping for multi-agent reinforcement learning. The Knowledge Engineering Review, 31(1):44-58, 2016.
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.
Sam Michael Devlin and Daniel Kudenko. Dynamic potential-based reward shaping. Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems, pp. 433 440. IFAAMAS, 2012.
Nat Dilokthanakul, Christos Kaplanis, Nick Pawlowski, and Murray Shanahan. Feature control as intrinsic motivation for hierarchical reinforcement learning. IEEE transactions on neural networks and learning systems, 30(1 11:31493443338 2019.
Yali Du, Lei Han, Meng Fang, Ji Liu, Tianhong Dai, and Dacheng Tao. Liir: Learning individual intrinsic reward in multi-agent reinforcement learning. 32, 2019.
Jakob N Foerster, Gregory Farquhar, Triantafyllos Afouras, Nantas Nardelli, and Shimon Whiteson. Counterfactual multi-agent policy gradients. In Thirty-second AAAI conference on artificial intelligence, 2018.
Drew Fudenberg and Jean Tirole. Tirole: Game theory, MIT Press, 726:764, 1991.
Anna Harutyunyan, Sam Devlin, Peter Vrancx, and Ann Nowé. Expressing arbitrary reward functions as potential-basee advice. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 29, 2015.
Ionel-Alexandru Hosu and Traian Rebedea. Playing atari games with deep reinforcement learning and human checkpoint replay. arXiv preprini arXiv: 1607.05077 2016.
Tommi Jaakkola, Michael Jordan, and Satinder Singh. Convergence stochastic iterative dynamic programming algorithms. In Advances in neural information processing systems, pp. 703-710, 1994.
Jakub Grudzien Kuba, Muning Wen, Yaodong Yang, Linghui Meng, Shangding Gu, Haifeng Zhang, David Henry Mguni, and Jun Wang. Settling the variance multi -ggett policy gradients. arXiv preprint arXiv: 108.0000.. 008.0808....... 2021.
10

---

Published as a conference paper at ICLR 2022
Tejas D Kulkarni, Karthik Narasimhan, Ardavan Sacedi, and Josh Tenenbaum. Hierarchical deep reinforcement learning: Integrating temporal abstraction and intrinsic motivation. Advances in neural information processing systems, 29:3675-3683, 2016.
Minne Li, Zhiwei Qin, Yan Jiao, Yaodong Yang, Jun Wang, Chenxi Wang, Guobin Wu, and Jieping Ye. Efficient ridesharing order dispatching with mean field multi-agent reinforcement learning. In The World Wide Web Conference. pp. 983-994, 2019.
Sergio Valcarcel Macua, Javier Zazo, and Santiago Zazo. Learning parametric closed-loop policies for markov potential games. arXiv preprint arXiv:1802.00880 2018.
Anuj Mahajan, Tabish Rashid, Mikayel Samvelyan, and Shimon Whiteson. Maven: Multi-agent variational exploration. arXiv preprini 1xXiv:1900004400 2019.
Patrick Mannion, Sam Devlin, Karl Mason, Jim Duggan, and Enda Howley, Policy invariance under reward transformations for multi-objective reinforcement learning. Neurocomputing, 263:60-73, 2017.
Patrick Mannion, Sam Devlin, Jim Duggan, and Enda Howley. Reward shaping for knowledge-basd multi-objective multi-agent reinforcement learning. The Knowledge Engineering Review, 33, 2018.
Laetitia Matignon, Guillaume J Laurent, and Nadine Le Fort-Piat. Independent reinforcement learners in cooperative markov games: survey regarding coordination problems. The Knowledge Engineering Review, 27(1):1-31, 2012.
David Mguni. A viscosity approach to stochastic differrnniall games of control and stopping involving impulsive control. arXiv preprint arXiv::803: /432, 2018.
David Mguni. Cutting your losses: Learning fault-tolerant control and optimal stopping under adverse risk. arXiv preprint arXiv: 1et:::902000000 2019.
David Mguni, Joel Jennings, and Enrique Munoz de Cote. Decentralised learning in systems with many, many strategic agents. In Thirty-Second AAAI Conference on Artificial Intelligence, 2018.
David Mguni, Joel Jennings, Sergio Valcarcel Macua, Emilio Sison, Sofia Ceppi, and Enrique Munoz de Cote. Coordinating the crowd: Inducing desirable equilibria in non-cooperative systems. arXiv preprint arXiv: 1092, 2019.
David Mguni, Yutong Wu, Yali Du, Yaodong Yang, Ziyi Wang, Minne Li, Ying Wen, Joel Jennings, and Jun Wang. Learning in nonzero-sum stochastic games with potentials. arXiv preprint 1:Xi::2003.09284, 2021.
Andrew Y Ng, Daishi Harada, and Stuart Russell. Policy invariance under reward transformations: Theory and application to reward shaping. In ICML, volume 99, pp. 278-287, 1999.
Bernt Øksendal. Stochastic differential equations. In Stochastic differential equations, pp. 65-84. Springer, 2003.
Georgios Papoudakis, Filippos Christianos, Lukas Schäfer, and Stefano V Albrecht. Comparative evaluation of multi-agent deep reinforcement learning algorithms. arXiv preprint arX1v:2006.07869, 2020.
Deepak Pathak, Pulkit Agrawal, Alexei A Efros, and Trevor Darrell. Curiosity-driven exploration by sulf-supervised prediction. In International Conference on Machine Learning (ICML), pp. 7778-7787, 2017.
P Peng, Q Yuan, Y Wen, Y Yang, Z Tang, H Long, Jnd Wang. Multiagent bidirectionally.coordinnaed nets for learning play stareraft combat games. arxiv 2017, arXiv preprint 1703 10069, 2017a.
Peng Peng, Ying Wen, Yaodong Yang, Quan Yuan, Zhenkun Tang, Haitao Long, and Jun Wang. Multiagent eddirectionally-cooriii coordinated nets: Emergence of human-level coordination in learning to play starcraft combat games. arXiv preprint arXiv: /703. 10069, 2017b.
11

---

Published as a conference paper at ICLR 2022
Emanuele Pesce and Giovanni Montana. Improving coordination in small-scale multi-agent deep reinforcement learning through memory-driven communication. Machine Learning, pp. 1-21, 2020.
Dawei Qiu, Jianhong Wang, Junkai Wang, and Goran Strbac. Multi-agent reinforcement learning for automated peer-to-peer energy trading in double-side auction market. In Proceedings of the Thirtieth International Joint Conference Artificial Intelligence, ICCAI, pp. 2913-2920, 2021.
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. In International Conference on Machine Learning, pp. 4295-4304, PMLR, 2018.
Tim Roughgarden and Eva Tardos. Introduction to the inefficiency of equilibria. Algorithmic Game Theory, 77:443-459, 2007.
Maryam Sadeghlou, Mohammad Reza Akbarzadeh-T, and Mohammad Bagher Naghibi-S. Dynamic agent-based reward shaping for multi-agent systems. In 2014 Iranian Conference on Intelligent Systems (ICIS), pp. 1-6. IEEE, 2014.
Mikayel Samvelyan, Tabish Rashid, Christian Schroeder De Witt, Gregory Farquhar, Nantas Nardelli, Tim GJ Rudner, Chia-Man Hung, Philip HS Torr, Jakob Foerster, and Shimon Whiteson. The starcraft multi-agent challenge. arXiv preprint arXiv: 1922.044002 2019.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. CoRR, abs/ 063407637777 2017.
Yoav Shoham and Kevin Leyton-Browe Multiagent systems: Algorithmic, game-theoretic, and logical foundations. Cambridge University Press, 2008
Kyunghwan Son, Daewoo Kim, Wan Kang. David Farl 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-decomposittin networks for cooperative multi-agent learning. arXiv preprint arXiv: 052966 2017.
John N Tsitsiklis and Benjamin Van Roy. Optimal stopping of markov processes: Hilbert space theory, approximation algorithms, and an application to pricing high-dimensional financial derivatives. IEEE Transactions on Automatic Control, 44(10):1840-188) 1999.
Alberto Viseras, Thomas Wiedemann, Christoph Manss, Lukas Magel, Joachim Mueller, Dmitriy Shutin, and Luis Merino. Decentralized multi-agent exploration with online-learning of gaussian processes. In 2016 IEEE International Conference on Robotics and Automation (ICRA), pp. 4222-4229. IEEE, 2016.
Jianhao Wang. Zhizhou Ren, Beining Han, Jianing Ye, and Chongjic Zhang. Towards understanding linear value decomposition in cooperative multi-agent lelannnnng arXiv preprint arXiv:2006.00 00587, 2020a.
Jianhao Wang, Zhizhou Ren, Terry Liu, Yang Yu, and Chongjie Zhang. Qplex: Duplex dueling multi-agent q-learning. arXiv preprint orXiv:2008.01062 2020b.
Jianhong Wang, Yuan Zhang, Tae-Kyun Kim, and Yunjie Gu. Shapley q-value: A local reward approach to solve global reward games. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 7285-7292, 2020c.
Jianhong Wang, Wangkun Xu, Yunjie Gu, Wenbin Song, and Tim Green, Multi-agent reinforcement learning for active voltage control power distribution networks. Advances in Neural Information Processing Systems, 34, 2021a.
Jianhong Wang, Yuan Zhang, Tae-Kyun Kim, and Yunjie Gu. Modelling hierarchical structure between dialogue policy and natural language generator with option framework for task-oriented dialogue system. In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net 2021b.
12

---

Published as a conference paper at ICLR 2022
Yaodong Yang and Jun Wang. An overview of multi-agent reinforcement learning from game theoretical perspective. arXiv preprint arXiv:2011.00583, 2020.
Yaodong Yang. Lantao Yu, Yiwei Bai, Jun Wang, Weinan Zhang, Ying Wen, and Yong Yu. A study of ai population dynamics with million-agent reinforcement learning. arXiv preprint arXiv:1709.04511 2017.
Yaodong Yang, Rui Luo, Minne Li, Ming Zhou, Weinan Zhang, and Jun Wang. Mean field multi- agent reinforcement learning. In International Conference on Machine Learning, pp. 5571-5500 PMLR, 2018.
Yaodong Yang, Ying Wen, Jun Wang, Liheng Chen, Kun Shao, David Mguni, and Weinan Zhang. Multi-agent determinantal q-learning. In International Conference on Machine Learning, pp- 10757-10766. PMLR, 2020.
Chao Yu, Akash Velu, Eugene Vinitsky, Yu Wang, Alexandre Bayen, and Yi Wu. The surprising effectiveness of mappo in cooperative, multi-agent games. arXiv preprint arXiv:2103.012 00000555... 2021.
Zeyu Zheng, Junhyuk Oh, and Satinder Singh. On learning intrinsic rewards for policy gradient methods. In Advances Neural Information Processing Systems (NeurIPS), 2018.
Meng Zhou, Ziyu Liu, Pengwei Sui, Yixuan Li, and Yuk Ying Chung. Learning implicit credit assignment for multi-agent actor-critie. arXiv e-prints, pp. uxXiv-2007, 2020a.
Ming Zhou, Jun Luo, Julian Villella, Yaodong Yang. David Rusu, Jiayu Miao, Weinan Zhang, Montgomery Alban, Iman Fadakar, Zheng Chen, et al. Smarts: Scalable multi-agent reinforcement learning training school for autonomous driving. arXiv preprint arXiv:2010.09776, 2020b.
Martin Zinkevich, Amy Greenwald, and Michael Littman. Cyclic equilibria in markov games. Advances in Neural Information Processing Systems, 18: 18:1641, 2006.
13


Reviews:
[{"review_id": "xh2qSTDi9Cr", "reviewer": "Reviewer_nTCC", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is well written and relatively easy to follow, although the notation is at time heavy. This reviewer noted the extensive support material, including relevant material for reproducing the experiments, an ablation study and further the mathematical derivations to support the work. I could not go through section 14 containing the proofs of the technical results, which are several pages of extensive mathematical notation. So I cannot comment on the correctness and I wonder whether such an extensive material is really essential, although as part of the support material does not affect the fruition of the main paper.\n\n[General readability] In section 3, paragraph 1, \"the system is in a state s and each agent takes an action a”. The concept of “system” is not defined here. At first, I would assume that it is one agent, and not a system, that can be in a state. Similarly, as I came to the concept of joint-action, it was not clear to me as I was under the impression that each agent makes one individual choice. Also unclear is how a joint action can produce a reward for one agent, and lead to one transition since a I previously assumed a transition to defined for a state-action pair, and not a state-multiple-actions pair. This lack of clarity might be due to my limited familiarity of this very particular setup, but I feel that other readers in the area of RL could benefit from a slightly more explicit explanation on this point. \n\n\nMy main observation is that more explanations would be beneficial in relation to  how the properties of the algorithm described in section 6 relate to the experimental evidence in section 7. In particular, what specific aspects of the simulations complement the theoretical discussion above, and in which way? Are the experiment meant to assess specific metrics of interest, to provide a quantitative advantage over existing SOTA algorithms in the proposed benchmarks? Or else? While the narrative appears to assume that the answer to these questions are self-evident, I would argue that more justifications on the precise aims of both theoretical and experimental evidence would strengthen the paper.\n\nI would have liked to read more about the limitations and drawback of the proposed approach in relation to existing algorithms, in particular those used for comparison. While performance is improved, what is the price to pay for that, if any? Are there particular implications from a computational perspective that need to be considered? Considerations on tuning hyper-parameters, or other elements that could help appreciate possible limitations?  \n\n\n", "summary_of_the_paper": "The paper describes a novel reinforcement learning algorithm for multi-agent system (MARL) that employs a generator of intrinsic reward and a switching control system that helps to regulate intrinsic control. Crucially, the intrinsic reward is learned to better fit the particular task being learned. The paper claims that the proposed algorithm helps with exploration as well as preservation of known policies. The paper has a strong theoretical background with a section that illustrates the properties of convergence and optimality. The experimental results appear to justify the approach with superior performance with respect to the baselines. The paper deals with an emerging and interesting area of RL and proposes a new mechanism for co-ordinated RL agents. \n", "summary_of_the_review": "This is a solid paper that proposed a promising approach to MARL. Many details in the paper require extensive examination, care, and previous knowledge. The paper is fairly notation-heavy, but it makes a fair effort to explain concepts also in plain English. The results are promising and I believe it can provide a valid contribution to ICLR. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "gdjJyyEPpXr", "reviewer": "Reviewer_crmy", "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": "As fas as the reviewer is concerned, the proposed method is novel. However, there are some drawbacks that can be improved.\n\n***Soundness***\n\nThe objective of Generator contains four terms: (1) environmental rewards, (2) learned intrinsic rewards, (3) rewarding costs, and (4) a RND-style exploration bonus. Learning incentivizing policies of Generator may not be easier than learning without it because the Generator faces a large space that has a similar size of joint action-observation space.\n\nSome claims need more consideration. For example, the authors hold that \"CT-DE methods are however, prone to convergence to suboptimal joint policies (Mahajan et al., 2019). ... In such situations, (random) occurrences of successful coordination are improbable, moreover value factorisations, e.g. QMIX (Rashid et al., 2018), cannot represent non-monotonic team rewards.\" Not all CTDE methods have this problem. QTRAN, QTRAN++, weighted QMIX, and QPLEX can represent non-monotonic Qs and are free from the issue in Mahajan's paper.  The reviewer recommend rewriting the third paragraph of the Introduction section to better motivate the proposed method\n\nDiscussion of related works should be improved. For example, there are many multi-agent exploration methods expect for MAVEN, and previous works on learning (or designing) multi-agent intrinsic rewards (e.g., using transformers or curiosity-based intrinsic rewards) should be discussed. \n\n***Evaluation***\n\nThe reviewer was expecting an ablation study regarding the exploration bonus. Previous work has shown that RND works well on SMAC. The reviewer would increase the score if the authors can prove that LIGS performs relatively well without the RND-like objective.\n\n", "summary_of_the_paper": "The paper focuses on learning intrinsic rewards for multi-agent reinforcement learning, which is an important problem. Different from previous works on this topic, the authors propose to train an agent with a learnable gating function that incentives other agents. Theoretical analysis and empirical evaluation are provided to prove the effectiveness of the proposed method.", "summary_of_the_review": "The reviewer finds the idea novel and the method solid. However, the empirical evaluation, the discussion of related works, and the presentation of the paper can be further improved.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "JHxYyD85vgA", "reviewer": "Reviewer_W87Z", "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": "The first thing that needs to be said about this paper is that it is hard to read. There are several elements that lead to this overall conclusion:\n- There are many small errors, inconsistencies, and unnecessary elements in the text and equations.\n- The presentation of the contribution is smeared out over several pages, instead of providing one clear overview followed by further details where necessary.\n- The paper needs some language editing.\n\nExamples of the small issues with the text (this is not meant to be an exhaustive list, I would ask the authors to critically re-read and edit their work):\n- Section 3, second line: does the set $\\mathcal{N}$ contains the indices $1$ through $N$, or the agents? It seems that in most places where you refer to $\\mathcal{N}$, the sentence would be just as clear without it.\n- Section 7.2: you promise four SMAC maps, and then list (and show results on) only three\n- Algorithm 2:\n  - Line 1: what is $\\pi_0$? Is it the set of agent policies {$\\pi^i_0$}? \n  - Line 3 is informative, please have a similar line for the second loop starting on line 16.\n  - Lines 8-9, 15, 18: are $g_t$ and $q_t$ the same?\n  - Input: the parameters of $h$ and $\\hat{h}$ are probably $\\theta_h$ and $\\theta_\\hat{h}$\n  - Lines 18-21: no need for control flow here, that's taken care of by $r_t^i$ being zero if $q_t$ is zero itself.\n  - What happens on line 27?\n  - Section 4.2, which is supposed to show the learning algorithm (PPO), does not seem to be present in the paper. Section 4, for which the same claim is made, does not introduce PPO.\n- Page 18 (section / Appendix 14): in the long derivation, there are inconsistencies in how $t$ is shifted to $t+1$. It is also not clear to me where the the last term on the second line comes from. In the second half of that derivation, a capital $K$ appears, without it being made clear what it means. As it stands, I'm not convinced of the correctness of that derivation. \n\nIn spite of the errors and inconsistencies, I found Algorithm 2 to be the best presentation of the paper’s contribution. Please consider replacing sections 3-5 in the main text with a corrected version of Algorithm 2.\n\nAll that being said, the results do look promising, and the method is interesting. Some more detailed comments and requests:\n- While the results look good, MAPPO isn’t quite state of the art. Please compare to something that beats MAPPO, e.g. EMC, https://openreview.net/forum?id=cLYyCXHU7g1n.\n- The paper's contribution could be more significant if a bit more time/space was spent on the results (this should not be a problem if the presentation of the method is condensed). In particular investigating how the method works in practice and in that way answering the question why it actually works would be very valuable. Suggested questions to answer (this might be done with the gridworld environments):\n  - What does the exploration reward generator actually learn? What does it reward?\n  - What does the gate / switching control mechanism learn? When does it switch on and off?\n\nOther comments:\n- ‘Novel framework’ sounds a bit grand. The centralized exploration shaping reward that is introduced looks like a good idea, but it’s not a novel framework.\n- Central coordination of exploration, like the method here is doing, reduces the independence of the agents. Centralized training in general does that too, though, and there are no gradients between the agents being introduced here, so it seems okay. But it’s good to clearly position the contribution in this respect; the method does further reduce the independence, and thereby the multi-agent aspect of MARL.\n- The fact that the gate is binary seems targeted to environments like the gridworld. Have you experimented with a continuous gate, or no gate at all? What are the states in the SMAC environments where it switches on? More generally, what are the assumptions that make the switching work?\n", "summary_of_the_paper": "This paper introduces a learned centralized exploration reward for multi-agent settings. The exploration reward is factorized into an on/off gate (dubbed ‘switching control’) and a scale function. Some mathematical derivations are included (sketched in the main text, with details in the appendices) to provide theoretical guarantees on how the exploration reward changes the solutions the training procedure might find. Evaluations on gridworld environments that target specific difficulties of multi-agent exploration show promising results. Some maps from the SMAC benchmark are also included, and again show good results.", "summary_of_the_review": "While the results look good, the text and equations are unclear. My current recommendation is to reject the paper, because the presentation quality falls short of the expected standard. However, there are interesting aspects to the proposed method, and the results look promising. If the presentation is improved significantly, I would be open to recommending a weak accept. I would strongly recommend to the authors to condense the presentation of the method in the main text and spend more time on evaluating the method. With more evaluation and clarification of how the method functions in practice, and if the further results are also good, I would consider raising my recommendation to accept.\n\nEDIT: the resubmission addresses a significant portion of my readability concerns, I'm raising my score to a weak accept.", "strength_and_weaknesses": "", "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": "7y0BsqrejgQ", "reviewer": "Reviewer_vU2u", "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": "From the perspective of learning intrinsic rewards and preserving the optimality, instead of hand-craft intrinsic rewards, it is a worthwhile investigation direction.\n\nHowever, there are some confusions about the method and experiments. If all these concerns are addressed well by the authors, I am willing to increase the score.\n\nFirst, I think the challenges mentioned in Section 1 are redundant. The first two points can be concluded into one point.\n\nSecond, in common, each agent should have its own reward function R_i(o_i,a_i), not from the global reward function. Only if each agent receives the team reward at each step, each agent’s objective is to maximize the team reward. However, in this paper, each agent maximizes its own expected return. Especially, this paper assumes some setting that each agent’s reward is non-monotonic to the team reward. Therefore, it is not suitable to obtain an individual reward from the global reward function.\n\nThird, about the switch controls, I am confused about equation 2, where it uses I_t, while how to calculate or define I_t is not described. Instead, I_{\\tau_{k+1}} is defined as the reverse value of I_{\\tau_{k}}. Does this mean at each step, if I_t is 1, the value of I_{t+1} at the next state will switch to 0, and vise versa? Why is this changing flow? How does it find important states? And as a consequence, why equation 2 can be reformulated as equation 3 is confusing.\n\nWhat does ” Generator constructs intrinsic rewards that are tailored for the specific setting” mean?\n\nFinally, about the experiments, since I have a rich understanding of starcraft II, I am concerned that the selected maps in starcraft II may not well support the method. In these maps, just simply increase the exploration rate, many MARL algorithms can achieve better results than that shown in this paper, which can also be found in [1].\n\nThere exists some typos throughout the paper. So I recommend authors repolish the paper to make it clearer.\nSuch as, “with bilevel approach” ->” with a bilevel approach”\n“Generator’s objective is:” repeats twice.\n“(potentially away from suboptimal trajectories, c.f. Experiment 2) and enable”  -> enables\n\n[1] Revisiting the Monotonicity Constraint in Cooperative Multi-Agent Reinforcement Learning. 2021\n", "summary_of_the_paper": "This paper proposes a method, Learnable Intrinsic-reward Generation Selection (LIGS) to improve coordinated exploration. LIGS incorporates an extra agent, called Generator to learn what state to give what intrinsic reward for each agent. The intrinsic reward is potential-based, so it preserves the optimality. Experimental results on several domains show its advantages over several MARL methods.\n", "summary_of_the_review": "From the perspective of learning intrinsic rewards and preserving the optimality, instead of hand-craft intrinsic rewards, it is a worthwhile investigation direction.\n\nHowever, there are some concerns about the method and experiments needed to be addressed. So I give a borderline reject currently. If all these concerns are addressed well by the authors, I am willing to increase the score.", "strength_and_weaknesses": "", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper addresses coordination improvement in the MARL setting by learning intristic rewards that motivate the exploration and coordination. The  paper is theoretically founded and the empirical evaluations back up the claims.

During the rebuttal the carried out an impressive amount of work. They provided several additional studies and substantially improved the presentation, addressing all of the reviewers' requests. Although not all the reviewers responded to the authors, the authors' response was taken into the account when recommending the decision.

Minor:
- The authors should comment on the learning intristic rewards with evolution (Faust et al, 2019): https://arxiv.org/abs/1905.07628
Decision: Accept (Poster)