RPM: Generalizable Multi-Agent Policies for Multi-Agent Reinforcement Learning
Authors: Wei Qiu
Xiao Ma
Bo An
Svetlana Obraztsova
Shuicheng YAN
Zhongwen Xu
Venue: ICLR 2023 poster (2023)
Keywords: multi-agent system
multi-agent reinforcement learning

Abstract: Despite the recent advancement in multi-agent reinforcement learning (MARL), the MARL agents easily overfit the training environment and perform poorly in evaluation scenarios where other agents behave differently. Obtaining generalizable policies for MARL agents is thus necessary but challenging mainly due to complex multi-agent interactions. In this work, we model the MARL problem with Markov Games and propose a simple yet effective method, called ranked policy memory (RPM), i.e., to maintain a look-up memory of policies to achieve good generalizability. The main idea of RPM is to train MARL policies via gathering massive multi-agent interaction data. In particular, we first rank each agent’s policies by its training episode return, i.e., the episode return of each agent in the training environment; we then save the ranked policies in the memory; when an episode starts, each agent can randomly select a policy from the RPM as the behavior policy. Each agent uses the behavior policy to gather multi-agent interaction data for MARL training. This innovative self-play framework guarantees the diversity of multi-agent interaction in the training data. Experimental results on Melting Pot demonstrate that RPM enables MARL agents to interact with unseen agents in multi-agent generalization evaluation scenarios and complete given tasks. It significantly boosts the performance up to 818% on average.

Published as a conference paper at ICLR 2023
RPM: GENERALIZABLE MULTI-AGENT POLICIES FOR MULTI-AGENT REINFOR LEARNING
Wei Qiu Xiao Ma' Bo An Svetlana Obraztsova Shuicheng Yan' Zhongwen Xu
*Nayyang Technological University giuw00086e .tu. edu........ sg
'Sea AI Lab
zhongwen.. s xwwgmaiil.ccoo com
ABSTRACT
Despite the recent advancement in multi-agent reinforcement learning (MARL), the MARL agents easily overfit the training environment and perform poorly in evaluation scenarios where other agents behave differently. Obtaining generalizable policies for MARL agents is thus necessary but challenging mainly due to complex multi-agent interactions. In this work, we model the MARL problem with Markov Games and propose a simple yet effective method, called ranked policy memory (RPM), i.e., maintain look-up memory of policies achieve good generaliz- ability. The main idea of RPM to train MARL, policies via gathering massive multi-agent interaction data. In particular, we first rank each agent's policies by its training episode return, i.e., the episode return of each agent in the training environment; we then save the ranked policies in the memory; when an episode starts, each agent can randomly select policy from the RPM as the behavior policy. Each agent uses the behavior policy to gather multi-agent interaction data for MARL training. This innovative self-play framework guarantees the diversity of multi-agent interaction in the training data. Experimental results on Melting Pot demonstrate that RPM enables MARL agents to interact with unseen agents in multi aueti-agentt generalization evaluation scenarios and complete given tasks. It significantly boosts the performance up to 818% average.
INTRODUCTION
In Multi-Agent Reinforcement Learning (MARL) (Yang Wang 2020), each agent acts decentrally and interacts with other agents to complete given tasks or achieve specified goals via reinforcement learning (RL) (Sutton & Barto 2018). In recent years, much progress has been achieved in MARL
research (Vinyals et al.) 2019 Jaderberg et al.) 2019 Perolat et al., 2022). However, the MARL
agents trained with current methods tend to suffer poor generalizability (Hupkes et al.. 2020) in the new environments. The generalizability issue is critical to real-world MARL applications (Leibo et al. 2021), but is mostly neglected in current research.
In this work, aim train MARL agents that can adapt new scenarios where other agents' policies are unseen during training. We illustrate a two-agent hunting game as an example Fig. [ The game's 's objective for two agents is to catch the stag together, catch the stag and risks being killed. They may perform well in evaluation scenarios similar to the training environment, as shown in Fig. D (a) and (b), respectively, but when evaluated in scenarios different from the training ones, these agents often fail. As shown in Fig. (c), the learning agent (called the focal agent following (Leibo et al.) 202T)) supposed to work together with the other agent (called the background agent also following (Liboo et al. (02T)) that is pre-trained and can capture the hare and the stag. In this case, the focal agent would fail to capture the stag without help from its teammate. The teammate of the focal agent may be tempted to catch the hare alone and not cooperate, or may only choose to cooperate with the focal agent after capturing the hare. Thus, the focal agent should adapt to their teammate's 's behavior to catch the stag. However, the policy of the background agent is unseen to the focal agent during training. Therefore, without generalization, the agents trained Fig. (left) cannot achieve optimal policy in the new evaluation scenario.
agent acting alone cannot
Wei Qiu did the work while interning Sea AT Lab. Corresponding author.

---

Published as a conference paper at ICLR 2023
Two agent Hunting Game
Both agents catch the stag
Focal agent behaves poorly
Focal agent
Background
agent
Training environment
Conventional evaluation protocol: evaluating two agents together
New evaluation protocol: evaluate the the focal agent only
(a)
(b)
(c)
Figure I: Two-Agent Hunting Game. (a) Training environment. Two agents (hunters) hunt in the environment. (b) After training in the training environment, all agents behave cooperatively capture the stag. (c) In the new evaluation scenario, one agent is picked as the focal agent (in the magenta circle) and paired with a pre-trained agent (in the brown circle) that behaves in different ways to evaluate the performance of the selected agent. In conclusion, the conventional evaluation protocol fails to evaluate such behavior and current MARL methods easily fail to learn the optimal policy due the lack of diversified multi-agent interaction data during training.
Inspired by the fact that human learning is often accelerated by interacting with individuals of diverse skills and experiences (Meltzoff et al., 2009: [Tomasello 2010), we propose a novel method aimed at improving the generalization of MARL through the collection of diverse multi-agent interactions. Concretely, we first model the MARL problem with Markov Games (Littman) 1994) and then propose simple yet effective method called ranked policy memory (RPM) to attain generalizable policies. The core idea of RPM is to maintain a look-up memory of policies during training for the agents. In particular, first evaluate the trained agents' policies after each training update. We then rank the trained agents' policies by the training episode returns and save them in the memory. In this way, we obtain various levels, i.e., the performance of the policies. When starting an episode, the agent can access the memory and load a randomly sampled policy to replace the current behavior policy. The new ensemble of policies enables the agents in self-play to collect diversified experiences in the training environment. These diversified experiences contain many novel multi-agent interactions that can enhance the extrapolation capacity of MARL, thus boosting the generalization performance. We note that an easy extension by incorporating different behavior properties as the keys in RPM could potentially further enrich the generalization but it is left for future work.
We implement RPM on top of the state-of-the MARL algorithm MAPPO (Yu et al. (021). ). To verify its effectiveness, we conduct large-scale experiments with the Melting Pot (Leibo et al. 2021], which is well-recognized benchmark for MARL generalization evaluation. The experiment results demonstrate that RPM significantly boosts the performance of generalized social behaviors up to 818% on average and outperforms many baselines in variety of multi-agent generalization evaluation scenarios. Our code, pictorial examples, videos and experimental results are available at this link: https: //sp:://siii tes. goo. e. wwwmvviiieeeeeeeeeocooooeooceeoe wpm-iccll200000 ic1r2023
2 PRELIMINARIES
Markoy Games. We consider the Markov Games Littman 1994) represented by a tuple G = (W S. A, O, P, R, 7, p). A is set of agents with the size [ N; S is set of states; A X A is set of joint actions with A; denoting the set of actions for an agent i; O = , O, is the observation set, with O₂ denoting the observation set of the agent i; P S A S is the transition function and R = x
is the reward function where r; S x A + R specifies the reward for the agent given the state and the joint action; 7 the discount factor, the initial states are determined by a distribution p S + [0. 1]. Given state S, each agent i E N chooses its action u; and obtains the reward r(s, u)) with the private observation o; E O, where u = {u, } is the joint action. The joint policy of agents is denoted as Te { 1= where тe. SS x A. + [0. is the policy for the agent i. The objective of each agent is to maximize its total expected return R; = oc
E y'r
Multi-Agent RL. In MARL, multiple agents act in the multi-agent systems to maximize their respec- tive returns with RL. Each agent's policy n. optimized by maximizing the following objective:
J Jm.)) & E E -p
Σ
where [(T.) is performance measure for policy gradient RL methods (Williams 1992 Lillicrap et al.] 2016 Fujimoto et al. 2018). Each policy's Q value Q: is optimized by minmiizng the Tollowing regression loss (Mnih al. 2015) with TD-learning (Sutton 1984):
C(O.) A ED
(vi Qi, (st, un, s6, st,
2

---

Published as a conference paper at ICLR 2023
Agent policies
Policies of focal agents
Policies of background agents
Ke,
TT2
Substrate
Mea
16
Scenario
Interaction
Collect data
Interaction
Substrate
MARL Training
Rea
Collect data
Update
(Ta,
11=1
Multi-Agent Training
Multi-Agent Evaluation
All six agents' policies are trained with the MARL.. Right: Two agents with policies Tæ, and Tæs are picked as background agents, and the rest of the four agents (with new indices) are focal agents to be evaluated. The Tocal and the background agents constitute the evaluation scenario.
Figure 2: An example of our formulation. Left::
where yf = r + maxx Qú (st+1, ui, st, w/t). 0; are the parameters of the agents. 0, is the parameter the target Q' and periodically copied from 0. D' a sample from the replay buffer D.
3 PROBLEM FORMULATION
We introduce the formulation of MARL for training and evaluation in our problem. Our goal is to improve generalizabiliby of MARL policies in scenarios where policies of agents or opponents are unseen during training while the physical environment unchanged. Following Leibo al. (202I),
the training environment is defined as substrate. Each substrate is an N-agent partially observable Markov game Each agent optimizes its policy ne, via the following protocol.
Definition (Multi-Agent Training). There are N agents act in the substrate, which is denoted as G. Each agent receives partial environmental observation not known other agents and aims to opti- mizes its policy Te, by optimizing its accumulated rewards: Ei rrr The performance of the joint policy no { N measured by the mean individual return: R( (T)) = N ΣN R(TO,; 9).
R(TT, 9) measures the episode return of policy πı. in game G for agent i.
In order to evaluate the trained MARL policies evaluation scenario 9', we follow the evaluation protocol defined by Leibo al. 2021
Definition 2 (Multi-Agent Evaluation). There are M (1 < M S N 1) focal agents that are selected from N agents. The focal agents are agents to be evaluated in evaluation scenarios. They are paired with MM background agents whose policies के { NM were pre-trained with pseudo rewards in the same physical environment where the policies лe are trained. To measure the generalized performance in evaluation scenarios, we use the mean individual return of focal agents as the performance measure: R (M
EM R(TT,;9')
We show an example of our formulation in Fig. Note that the focal agents cannot utilise the interaction data collected during evaluation to train finetune their policies. Without training the policies of focal agents with the collected trajectories during evaluation, the focal agents should behave adaptively to interact with the background agents complete challenging multi-agent tasks. It
also worth noting that the ad-hoc team building (Stone & Kraus) 2010 Gu et al. (202T) is different from our formulation both in the training and evaluation. We discuss the differences in the related works section (Paragraph 3, Sec. 7).
In MARL, the focal agents need adaptively interact with background agents to complete given tasks. Formally, define the objective for optimizing performance of the focal agents without exploiting their trajectories in the evaluation scenario for training the policies { J.M.
M
max [( MM A max B 10000 mppiro Daro al ~ (16, M.M
(I)
M
4 RANKED POLICY MEMORY
To improve the generalization of MARL, agents in the substrate must cover as much multi-agent interactions, i.e., data, that resemble the unseen multi-agent interactions in the evaluation scenario.
However, current training paradigms, like independent learning (Tampuu al. 2017) and centralized
3

---

Published as a conference paper at ICLR 2023
RPM
MARL Training
Multi- Agent Evaluation
Pretrained policy
data
Rank
Rank 2
Rank
MARL Learner
Update RPM
Agent
Agent
Agent
Sampled policies
Focal Agents &
Background apent
Save policies of Na... and vé, given mean individual return
(1) Training episode return; (2) 9, 9;
The workflow of RPM for three-agent substrate. In the workflow, there are three agents in the substrate. Agent 3 is the background agent. Agents and 2 focal agenis.
Figure 3:
training and decentralized execution (CTDE) (Oliehoek et al. 2008), cannot give diversified multi- agent interactions, as the agents' policies are trained at the same pace. To this end, we propose a Ranked Policy Memory (RPM) method to provide diversified multi-agent behaviors.
RPM Building & Updating, We denote an RPM with V, which consists of Rmox entries, i.e., ranks, where max is the maximum training episode return (the episode return in the substrate). When an agent is acting in the substrate, it will receive the training episode return R. of all agents with policies ( (T Then {m)) are saved into V by appending agents' policies into the corresponding memory slot, V/ [re] .add ( ( J.V ). To avoid there being too many entries in the policy memory caused by continuous episode return values, we discretize the training episode return. Each discretized entry is covers range of [H, K + v)), where to > 0 and it can be either integer float number. For the training episode return R, the corresponding entry & can be calculated by:
[R/0] 1[(R mod v) + 0} x vb if 0, [R/#] v
otherwise.
where 1 is the indicator function, and 1-] is the floor function. Intuitively, discretizing R saves memory and memorize policies of similar performance in to the same rank. Therefore, diversified policies be saved to be sampled for agents.
RPM Sampling. The memory stores diversified policies with different levels of performance. We sample various policies of different ranks and assign each policy each agent in the substrate to collect multi-agent trajectories for training. These diversified multi-agent trajectories can resemble trajectories generated by the interaction with agents possessing unknown policies in the evaluation scenario. At the beginning of an episode, we first randomly sample N keys with replacement and then randomly sample one policy for each key from the corresponding list. All agents' policies will be replaced with the newly sampled policies for multi-agent interactions in the substrate, thus generating diversified multi-agent trajectories.
The Workflow of RPM. We showcase an ex- ample of the workflow of RPM Fig.3] There are three agents in training. Agents sample policies from RPM. Then agents collect data in the substrate for training. The train- ing episode return is then used to update RPM. During evaluation, agents and 2 are selected as focal agents and agent is selected as the background agent. We present the pseudo-code of MARL training with RPM in Algorithm | In Lines 45 the тe. is updated by sampling policies from RPM. Then. new trajectories of
Algorithm 1: MARL with RPM
Input:
Initialize To. V D, and G':
2 Input: Initialize behavior policy ne, +- me: for each update do
if RPM sampling then
To, Samp Samp+mmmmlgeeeee ingRPM
D < Gather Gatherrraaectories (Te,,
To <- MARITrainig (mo. D);
<- UpdateRPM (no, V,9);
R t- Rvaluate ( g');
Te, πa:
" Output: no-
D are collected in Line 6 πe trained in Line 7 with MARL method by using the newly collected trajecotries and Te, is updated with the newly updated πe. RPM updated Line 8 After that, the performance of nо is evaluated in the evaluation scenario G' and the evaluation score R is returned in Line
Discussion. RPM leverages agents' previously trained models in substrates to cover as many patterns of multi-agent interactions as possible to achieve generalization of MARL agents when paired with agents with unseen policies in evaluation scenarios. It uses the self-play framework for data collection. Self-play (Brown 1951; Heinrich et al.) 2015 Silver et al. 2018 Baker et al. 2019) maintains memory of the opponent's is previous policies for acquiring equilibria. RPM differs from other self-play
methods in four aspects: (i) self-play utilizes agent's previous policies create fictitious opponents
4

---

Published as a conference paper at ICLR 2023
when the real opponents are not available. By playing with the fictitious opponents, many fictitious data are generated for training the agents. In RPM, agents load their previous policies to diversify the multi-agent interactions, such as multi-agent coordination and social dilemmas, and all agents' policies are trained by utilizing the diversified multi-agent data. (ti) Self-play does not maintain explicit ranks for policies while RPM maintains ranks of policies. (iii) Self-play not introduced for generalization of MARL while RPM aims to improve the generalization of MARL. In Sec. 6 we also present the evaluation results of a self-play method.
MARL TRAINING
We incorporate RPM into the MARL training pipeline. We take MAPPO YYu et al. 2021 for instan- tiating our method, which is multi-agent variant of PPO (Schulman et al. 2017) and outperforms many MARL methods (Rashid al.) 2018 2020; Wang et al. 202 la) in various complex multi-agent domains. In MAPPO, a central critic is maintained for utilizing the concealed information of agents to boost agent learning due non-stationarity. RPM introduces novel method for agents to collect experiences/ttaaeccooiis T = [T,) Each agent optimizes the following objective:
J(H:) = E [min (nt (0)) 4!, clip (v) (0)) - ,,1+ c) :4)]]
(3)
where (f.) = Faf (v(1+(
Topu (w5l7 denotes the important sampling weight. The cl clip (.) clips the values of 0³ that are outside the range - e, + and is hyperparameter. A is a generalized advantage estimator (GAE) (Schulman et al. 2015). To optimize the central critic Vyl ((o), wf) we mix agents' observation-actin pairs and output an N-head vector where each value corresponds to the agent's value:
((+b) EDIND
[(v Vi Vo u ")))
(4)
where Yt- Eizo 7/r/t/ + V (to, 2( i=1 is vector of k-step returns, and D' is sample from the replay buffer D. In complex scenarios, egg., Melting Pot, with an agent's observation as input, its action would not impact other agents' return, since the global states contain redundant information that deteriorates multi-agent learning. We present the whole training process, the network architectures of the agent and the central critic in Appx. D
EXPERIMENTS
In this section, to verify the effectiveness of RPM improving the generalization of MARL, we conduct extensive experiments on Melting Pot and present the empirical results. We first introduce Melting Pot, baselines and experiment setups. Then we present the main results of RPM. To demonstrate that &a is important for RPM, we conducted ablation studies. We finally showcase case study to visualize RPM. To sum up, we answer the following questions: Q1: Is RPM effective in boosting the generalization performance of MARL agents? Q2: How does the value of impact RPM training? Q3: Does RPM gather diversified policies and trajectories?
6.1 EXPERIMENTAL SETUP
Melting Pot. To demonstrate that RPM enables MARL agents to learn generalizable behaviors, we carry out extensive experi- ments on DeepMind's 's Melting Pot (Leibo et al.) (022). Melting Pot is a suite of testbeds for the generalization of MARL meth- ods. It proposes a novel evaluation pipeline for the evaluation of the MARL method in various domains. That is, all MARL agents are trained in the substrate; during evaluation, some agents are selected the focal agents and the rest agents be- come the background agents (pre-trained policies of MARL models will be loaded); the evaluation scenarios share the same physical properties as the substrates. Melting Pot environments possess many properties, such as temporal coordination and
Apenis
obs
Channnl
Figure 4: The green box to the lower left shows the agent's 's observation.
5

---

Published as a conference paper at ICLR 2023
Stag Hunt
Clean Up
Rationalizable Coordination Chicken Game
Pure Coordination
Prisoners' Dilemma
Figure 5: Melting Pot environments. More information be found in Appx.
Table 1: Propertics of Melting Pot environments. The first column shows the properties and the first row lists environments, / mark indicates the environment possessing the corresponding property while X mark stands for the environment that does not the corresponding property. Refer Appx. for more information.
Pure
Prisoners'
Rational
Stag Hunt
Clean Up
Chicken Game
Coordination
Dilemuna
Coordination
Temporal Coordination
X
x
Reciprocity
Deception
X
/
X
/
Fair Resource Sharing
X
X
X
Following
J
J
X V
Task Partitioning
X
X
Trust Partnership
X
X
X
Free Riding
X
X
X
X
X
free riding as depicted in Table II An agent performing well in such environments indicates that its behaviors exhibit these properties. Fig. + the agent's observation is shown in the green box the lower left of the state (i.e., the whole image). The agent is in the lower middle of the observation. The deep neural network architecture of the agent's policy shown on left. More information about substrates, scenarios, neural network architectures and training details be found in Appx.
Baselines. Our baselines are MAPPO (Yu et al.) 2021), MAA2C (Papoudakis et al. 202 l OPRE (Vezhnevets et al.] 2020), heuristic fictitious self-play (HFSP) (Heinrich) 2017; Berner et al. 2019) and RandNet (Lee et al. 2019). MAPPO and MAA2C are MARL methods that achieved outstanding performance in various multi-agent scenarios (Papoudakis al., 2021). OPRE was proposed for the generalization of MARL. RandNet is a general method for the generalization by introducing a novel component in the convolutional neural network. HFSP is general self-play method for obtaining equilibria competitive games, we use it by using the policies saved by RPM.
RL
train MARL policies and choose some evaluation scenarios from each substrate as our evaluation testbed. The properties of the environments listed in Table [ We train agents in Melting Pot substrates for 200 million frames with 3 random seeds for all methods. Our training framework is distributed with 30 CPU actors collect experiences and GPU for the learner learn policies. We implement our actors with Ray (Moritz et al. 2018) and the learner with EPyMARL (Papoudakis et al. 2021). We use mean-std to measure the performance shades stand for the standard deviation. Due to limited computation budget, it is redundant to compare our method with other methods, such as QMIX (Rashid et al.) 2018)) and MADDPG (Lowe) al. 2017) as MAPPO outperforms them. All experiments are conducted on NVIDIA A100 GPUs.
Training setup. We use 6 representative substrates (Fig.
all methods. The bold lines in all figures are mean values, and the
6.2 EXPERIMENT RESULTS
To answer Q1, present the evaluation results of 17 Melting Pot evaluation scenarios in Fig. Our method can boost MARL in various evaluation scenarios, which have different properties, as shown in Table In Chicken Game (CG) 1-2 (the number stands for the number of the evaluation scenario of Chicken Game), RPM outperforms its counterparts by a convincing margin. HFSP performs no better than RPM. RandNet gets around 15 evaluation mean returns on Chicken Game (CG) 1. MAA2C and OPRE perform nearly random (the red dash lines indicate the random result) in the two scenarios. In Pure Coordination (PC) 1-3, Rational Coordination (PC) 1-3 and Prisoners' Dilemma (PD) 1-3, most baselines perform poorly. In Stag Hunt (SH) 1 1-3 and Clean Up (CU) 1-2, MAPPO and MAA2C perform unsatisfactorily. We can also find that HFSP even gets competitive performance Stag Hunt (SH) 1-3, However, HFSP performs poorly in Pure Coordination (PC) 1-3, Rational Coordination (RC) 1-3 and Prisoners' Dilemma (PD) 1-3. Therefore, the vanilla self-play method camnot directly be applied to improve the generalization of MARL methods. In summary, RPM boosts the performance up to around 818% on average compared with MAPPO on 6 evaluation scenarios. To answer Q2, we present experimental results of the impact of ib and the sampling ratio in HFSP in the following.

---

Published as a conference paper at ICLR 2023
CG
CG opl 14.3
SH
SH
3
96.9
36.4
opt: 65.9
opt: 54.4
20
53.8
40
10-
10
0
0
50
100
150
200
50 100 150 200
50
100
150 260
0
30
160
150
200
50 100
150
200
50 100 150 200
Eval Return Mean
2
PC1
400
opt: 722.6
opt: 385.9
0.75
1opt
0.4 opt 3,2
1.0
opt: 3.2
opt: 55.7
200-
100
0.00
50
100
150 200
50
100 150 200
50 100 150 200
50 160
150
200
50 100 150
200
50 100 150 200
2
PD
1
RC
RC3
RPM (ours)
60.8
apt: 36.8
opt: 11.9
opt: 7.7
opt: 13:1
MAPPO
20
20
RandNet
10
OPRE
0
HFSP
0 50
100
150
200
50
100
150
200
50 100 150 200
50 100 150 200
50
100
150
200
Random Policy
Training Steps (million)
Figure 6: Evaluation results of RPM and baselines in 17 scenarios. The red dash horizontal lines indicate the results of random policy. The optimal (opt) values shown in each sub- figurr and were gathered from (Liioo) al., (021), which an exploiter generated. The exploiter was trained the evaluation scenarios with RL
methods, and training time steps were 1,000 M.
Chicken Game
Stag Hunt
Clean Up
Pure Coordination
Prisoners Diiemma
Rational Coordianation
4000
1500
750
750
Counts
2000
500
2000
250
500
1000
10
0
10
100
10
Training Episode Retums
Figure 7: Histograms of training episode returns.
6.3 ABLATION STUDY
The Impact of tb. To investigate which value of & has the greatest impact on RPM performance, we conduct ablation studies by (i) removing ranks and sampling from the checkpoint directly; (ii) reducing the number of ranks by changing the value of tb. As shown in Fig. without ranks (sampling policies without ranks randomly), RPM cannot attain stable performance some evaluation scenarios. Especially in Pure Coordination (PC) 1-3, the result is low and has a large variance. In RPM, choosing the right interval vé can improve the performance, as shown in the results of Pure Coordination (PC) 1- 3 and Prisoners' Dilemma (PD) 1-3, showing that the value of v is important for RPM. We summarize the results and values of &a Table 2 and Table 3
Type
Type
Type
RPM Ran_Ran
Random Policy
Eval Return Mean
0.75
PC
0.6
PC
1.00
PC3
PD
30
PD
30
PD
0.50
0.25
10
10
0.0
0.00
Training Steps (million)
Figure 8: Ablation Studies: the performance of RPM with types of v and Random sampling (without ranks).
Table 2: Ablation study: the averaged value of the last three Table 3: & values, 1² indicates the values of + used to get results in Fig.
evaluation episode returns. Curves are Fig.
Types of
Types of y
Eval Scenarios
RPM
Random
Eval Scenarios
2
1
Pure Coordination
0.78
0.18
0.33
0.39
0.42
Pure Coordination
0.01
0.1
0.5
Pure Coordination
0.16
Pure Coordination
0.01
0.1
Pure Coordination
0.70
0.19
0.37
0.33
0.42
Pure Coordination
0.01
0.1
0.5
Prisoners' 19.60
Prisoners' Dilemma
0.02
0.2
Prisoners' Dilemma
10.41
13.76
17.74
14.96
Prisoners' Dilemma
0.02
0.2
Prisoners'
Prisoners' Dilemma
0.02
0.2
The Sampling Ratio in HFSP HFSP shows comparable results in some scenarios in Figure 6 In Figure the sampling ratio of HFSP is 0.3. We are interested in studying the impact of the sampling
7

---

Published as a conference paper at ICLR 2023
RPM (ours)
H.SP-0.9
HF5P-0.7
HFSP-0.5
HFSP-0.3
HFSP-0.1
Randam Policy
CU2
PC1
PC
Eval Return Mean
250
0.5
0.5
0.0
0.0
0
50
100
150
200
0
50
100
150
200
0
50
100
150
200
50
100
150
200
PC 3
PD
PD
2
PD
10
20
20
100
200
100 150
200
50
150
50
150
200
Training Steps (million)
Figure 9: Ablation Studies: the results of HFSP with different sampling ratios.
Eve uaton Retum Mean
Stag Hunt
# of RPM keys in Stag Hunt (SH) 1
4.
Bardom
of ROM boys
distributio
10
600
200
50
100
150
200
25 St 75 100 203 Training Steps (millin)
25 50 75 100125 150175 200
5
10 15
Training Steps (million)
Training Steps (millinn
The ning Episode Returns
(a)
(b)
(c)
[dl
Figure 10: Results analysis. (a) The evaluation results of RPM on Stag Hunt (SH) I; (b) The number RPM keys during training: (c) The distribution of the keys of RPM during training: (d) The histogram of the keys of RPM at timestep 200M during training.
ratio in HFSP on evaluation performance. We conduct experiments in CU 1 and 2, PC 1 and 3 and PD and 3. The sampling ratio list is [0.9, 0.7,0.7.3,3 0.5, 0.3, 0.1). We use the default training setup and use 3 random seeds. HFSP shows comparable results in PC 2 and 3, but its performances are poor in CU 1 and 2 and PD and 3. As shown in Figure 9 HFSP heavily relies on the sampling ratio. HFSP should be carefully tuned on each substrate to attain good performance, which is not feasible. In contrast, RPM is stable (the sampling ratio is 0.5) on all substrates. HFSP can also perform well in substrates such as PC and PD, where the return-checke -cturn-checkpoitt count distribution is more uniform. The absence of ranks leads to the frequent sampling of policies with high count values in substrates that have skewed return-checkpoint count distribution, thereby reducing the diversity of training data. Such distributions typically comprise a large number of policies with suboptimal performance.
6.4 CASE STUDY
We showcase how RPM helps to train the focal agents to choose the right behaviors the evaluation scenario after training in the substrate. To illustrate the trained performance of RPM agents, we use the RPM agent trained on Stag Hunt and run the evaluation on Stag Hunt 1. In Stag Hunt, there are 8 agents. Each agent collects resources that represent 'hare' (red) 'stag" (green) and compares inventories in an interaction, i.e., encounter. The results of solving the encounter are the same the classic Stag Hunt matrix game. In this environment, agents are facing tension between the reward for the team and the risk for the individual. In Stag Hunt 1, One focal agent interacts with seven pretrained background agents. All background agents were trained to play the 'stag' strategy during the interaction The optimal policy for the focal agent is also to play 'stag', However, it is challenging for agents detect other agents' strategy since such behavior may not persist in the substrate. Luckily, RPM enables focal agents to behave correctly in this scenario.
To answer Q3, we present the analysis of RPM on the substrate Stag Hunt and its evaluation scenario SH 1 in Fig. TO We can find that in Fig. TO (b), the number of the keys in RPM is growing monotonically during training and the maximum number of the keys in RPM is over 20, showing that agents trained with RPM discover many novel patterns of multi-agent interaction and new keys are created and the trained models are saved in RPM. Meanwhile, the evaluation performance is also increasing in SH as depicted in Fig. 10 (a). In Fig. (c), it is interesting to that the distribution of the keys of RPM is expanding during training. In the last 25 million training steps, the last distribution of RPM keys covers all policies of different performance levels, ranging from 0 to 14. By utilizing RPM, agents can collect diversified multi-agent trajectories for multi-agent training. Fig. [O] (d) demonstrates the final histogram of RPM keys after training. There over 600 trained policies that have a small value of keys. Since agents should explore the environment at the early
"Tii preference was trained with pscudo rewards by Leibo et al. 2021 and the trained models are available this link: htttps://gt thub. com wtt.cc/ccceee.ee deepmi ne/me 1 i ingoot
8

---

Published as a conference paper at ICLR 2023
stage of training, it is reasonable to find that many trained policies of RPM keys have low training episode returns. After 50 million training steps, RPM has more policies with higher training episode returns. Note that the maximum training episode return of RPM keys is over 14 while the maximum mean evaluation return of RPM shown in Fig. TO (a) is around 14.
Our experiments show that training policies with good performance in the substrate is crucial for improving generalization performance in the evaluation scenarios. When MARL agents perform poorly in the substrate, the evaluation performance will also be inferior or random, making it hard to have diversified policies. We show the results in Appx. D
7 RELATED WORKS
Recent advances in MARL Yang & Wang 2020 Zhang et al. 2021) have demonstrated its success
in various complex multi-agent domains, including agget coordination (Lowe et al.
2017
Rashid et al.,
2018
Wang et al.) 20211), real-time strategy (RTS) games (Jaderberg ct al.
2019
Berner et al.
2019
Vinyals al., 2019). social dilemma (Leibo et al.) 2017| Wang et al.
2018
Jaques et al.
2019:
Vezhnevets et al. (220), multi-agent communication (Foerster et al. 2016 Yuan
ct 2022)) asynchronous multi-agent learning (Amato al., 2019 Qiu et al. (022); open-
environment (Stooke et al., 2021), autonomous systems (Hüttenrauch et al. 201 Peng al. 2021)
and game theory equilibrium solving (Lanctot et al. 2017: Perolat et al. 2022). Despite strides made
in MARL, training generalizable behaviors in MARL is yet to be investigated.
Recently, generalization in RL (Packer et al., 2018: Song et al. 2019 Ghosh et al. 2021 Lyle et al. 2022) has achieved much progress in domain adaptation (Higgins al. 2017) and procedurally generated environments (Lee et al. 2019 [gl et al.
2020 Zha et al. 2020). However, there are few works of generalization in MARL domains (Carion et al. 2019 Vezhnevets et al. 20200) Mahajan et al., 2022; McKee et al. 2022). Recently, Vezhnevets et al. (2020) propose hierarchical MARL method for agents to play against opponents it hasn't It seen during training. However, the evaluation scenarios are only limited to simple competitive scenarios. |Mahajan et al. (2022) studied the generalization in MARL empirically and proposed theoretical findings based on successor features (Dayan 1993). However, no method to achieve generalization in MARL was proposed in (Mahajan et al. 2022).
Ad-hoc team building (Stone & Kraus, 2010 Gu et al. 202T) models the multi-agent problem as a single-agent learning task. In ad-hoc team building, one ad-hoe agent is trained by interacting with agents that have fixed pretrained policies and the non-stationarity issue is not severe. However, in our formulation, non-stationarity is the main obstacle to MARL training. In addition, there is only one ad-hoc agent evaluated by interacting agents that are unseen during training, while there can be more than one focal agent in formulation defined in Definition 2 thus making formulation general and challenging. There has been a growing interest in applying self-play to solve complex games (Heinrich et al. 2015 Silver et al. 2018 Hernandez et al. 2019 Baker et al. 2019}; however, its value in enhancing the generalization of MARL agents has yet to be examined. Due to space constraints, we discuss meta-learning (Al-Shedivat et al. 2018 Kim al. [202]) and population-based training (Strouse et al. 2021 Lupu et al. 2021 Tang et al. 2021 works in Appx.
8 CONCLUSION, LIMITATIONS AND FUTURE WORK
In this paper, we consider the problem of achieving generalizable behaviors in MARL. We first model the problem with Markov Game To train agents that can interact with agents that possess unseen policies. We propose a simple yet effective method, RPM, to collect diversified multi-agent interaction data, We save policies in RPM by ranking the training episode return. Empirically, RPM significantly boosts the performance of MARL agents in various Melting Pot evaluation scenarios.
RPM's performance is dependent on the appropriate value of vb Several attempts may be needed to determine the correct value of di for RPM. We are interested in discovering broader measures for ranking policies that do not explicitly consider the training episode return. Recently, there has been a growing interest in planning in RL, especially with model-based RL. We are interested in exploring the direction of applying planning and opponent/teammate modelling for attaining generalized MARL policies for future work. Agents engaged in complex interactions in multi-agent scenarios. Devising novel self-play methods is our future direction.

---

Published as a conference paper at ICLR 2023
ETHICS STATEMENT
We addressed the relevant aspects in our conclusion and have conflicts of interest declare.
REPRODUCIBILITY STATEMENT
We provide detailed descriptions of our experiments in the appendix and list all relevant parameters in Table and Table in Appx. D
The code can be found at this link: htttps://sites. google
com/view/ rpm- cl r2023/
ACKNOWLEDGMENTS
We would like to thank the anonymous reviewers for their suggestions. We thank the support from Xinyi Wan, Jiahao Ji and Xiangfan Li of the infrastructure team at Sea AI Lab. Wei Qiu and Bo An supported by the National Research Foundation, Singapore under its Industry Alignment Fund - Pre- tre-posiiiining (IAF-PP) Funding Initiative. Any opinions, findings and conclusions or recommendations expressed in this material are those of the author(s) and do not reflect the views of National Research Foundation, Singapore.
10

---

Published as a conference paper at ICLR 2023
REFERENCES
Maruan Al- Al-Shedivat, Trapit Bansal, Yura Burda, Ilya Sutskever, Igor Mordatch, and Pieter Abbeel. Continuous adaptation via meta-learning in nonstationary and competitive environments. In International Conference Learning Representations, 2018.
Christopher Amato, George Konidaris, Leslie P Kaelbling, and Jonathan P How. Modeling and planning with macro-actions in decentralized pomdps. Journal of Artificial Intelligence Research, 64:817-859, 2019.
Pierre-Luc Bacon, Jean Harb, and Doina Precup. The option-critic architecture. In Proceedings of the AAAI Conference Artificial Intelligence, volume 31, 2017.
Bowen Baker, Ingmar Kanitscheider, Todor Markov, Yi Wu, Glenn Powell, Bob McGrew, and Igor Mordatch. Emergent tool use from multi-agent autocurricula. In International Conference Learning Representations, 2019.
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.
Christopher Berner, Greg Brockman, Brooke Chan, Vicki Cheung, Przemystaw Debiak, Christy Dennison, David Farhi, Quirin Fischer, Shariq Hashme, Chris Hesse, et al. Dota 2 with large scale deep reinforcement learning, arXiv preprint arXiv:1912.0663 2019.
George W Brown. Iterative solution of games by fictitious play. Act. Anal. Prod Allocation, 13(1): 374, 1951.
Nicolas Carion, Nicolas Usunier, Gabriel Synnaeve, and Alessandro Lazaric. A structured prediction approach for generalization in cooperative multi-agent reinforcement learning. Advances in Neural Information Processing Systems, 32, 2019.
Kyunghyun Cho, Bart Van Merriënboer, Dzmitry Bahdanau, and Yoshua Bengio. On the properties of neural machine translation: Encoder-decoder approaches. arXiv preprint arXiv:1409.122 2014.
Peter Dayan. Improving generalization for temporal difference learning: The successor representation. Neural Computation, 5(4): 1993.
Lasse Espeholt, Hubert Soyer, Remi Munos, Karen Simonyan, Vlad Mnih, Tom Ward, Yotam Doron, Vlad Firoiu, Tim Harley, lain Dunning, et al. Impala: Scalable distributed deep-rl with importance weighted actor-learner architectures. In International Conference on Machine Learning, pp- 1407-1416. PMLR, 2018.
Jakob Foerster, loannis Alexandros Assael, Nando de Freitas, and Shimon Whiteson. Learning communicate with deep multi-agent reinforcement learning. In Advances in Neural Information Processing Systems, pp. 2137-2145, 2016.
Scott Fujimoto, Herke Hoof, and David Meger. Addressing function approximation error in actor- critic methods. In International conference machine learning, pp. 1587-1596. PMLR, 2018.
Dibya Ghosh, Jad Rahme, Aviral Kumar, Amy Zhang, Ryan P Adams, and Sergey Levine. Why generalization in rl is difficult: Epistemic pomdps and implicit partial observability, Advances in Neural Information Processing Systems, 34, 2021.
Pengjie Gu, Mengchen Zhao, Jianye Hao, and Bo An. Online ad hoc teamwork under partial observability. International Conference on Learning Representations, 2021.
Johannes Heinrich. Reinforcement learning from self-play in imperfect-infommane games. PhD thesis. UCL (University College London), 2017.
Johannes Heinrich, Mare Lanctot, and David Silver. Fictitious self-play in extensive-form games. In International conference machine learning, pp. 805-813. PMLR, 2015.
11

---

Published as a conference paper at ICLR 2023
Daniel Hernandez, Kevin Denamganai, Yuan Gao, Peter York, Sam Devlin, Spyridon Samothrakis, and James Alfred Walker. generalized framework for self-play training. In 2019 JEEE Conference Games (CoG), pp. 1-8. IEEE, 2019.
Irina Higgins, Arka Pal, Andrei Rusu, Loic Matthey, Christopher Burgess, Alexander Pritzel, Matthew Botvinick, Charles Blundell, and Alexander Lerchner. Darla: Improving zero-shot transfer in reinforcement learning. In International Conference on Machine Learning, pp. 1480-1490. PMLR, 2017.
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 9(8): 1735-17888 1997.
Dicuwke Hupkes, Verna Dankers, Mathijs Mul, and Elia Bruni. Compositionality decomposed: how do neural networks generalise? Journal of Artificial Intelligence Research, 67:757-795, 2020.
Maximilian Hüttennauch, Adrian Šošié, and Gerhard Neumann. Guided deep reinforcement learn- ing for swarm systems. AAMAS 2017 Autonomous Robots and Multirobot Systems (ARMS) Workshop, 2017.
Maximilian Igl, Gregory Farquhar, Jelena Luketina, Wendelin Boehmer, and Shimon Whiteson. Transient non-stationarity and generalisation in deep reinforcement learning. International Conference on Learning Representations, 2020.
Max Jaderberg, Wojciech M Czarnecki, lain Dunning, Luke Marris, Guy Lever, Antonio Garcia Castaneda, Charles Beattie, Neil C Rabinowitz, Ari S Morcos, Avraham Ruderman, et al. Human- level performance in 3D multiplayer games with population-based reinforcement learning. Science, 364(6443):859 865,,65555-6 2019.
Natasha Jaques, Angeliki Lazaridou, Edward Hughes, Caglar Gulcehre, Pedro Ortega, DJ Strouse, Joel Z Leibo, and Nando De Freitas. Social influence as intrinsic motivation for multi-agent deep reinforcement learning. In International Conference on Machine Learning, pp. 5040-3049 PMLR, 2019.
Dong Ki Kim, Miao Liu, Matthew D Riemer, Chuangchuang Sun, Marwa Abdulhai, Golnaz Habibi, Sebastian Lopez-Cot, Gerald Tesauro, and Jonathan How. A policy gradient algorithm for learning to learn in multiagent reinforcement learning. In International Conference Machine Learning. pp. 5541-5550. PMLR, 2021.
Mare Lanctot, Vinicius Zambaldi, Audrunas Gruslys, Angeliki Lazaridou, Karl Tuyls, Julien Pérolat, David Silver, and Thore Graepel. A unified game-theoretic approach to multiagent reinforcement learning. Advances in Neural Information Processing Systems, 30, 2017.
Kimin Lee, Kibok Lee, Jinwoo Shin, and Honglak Lec. Network randomization: A simple technique for generalization in deep reinforcement learning. In International Conference Learning Representations, 2019.
Joel Z Leibo, Vinicius Zambaldi, Mare Lanctot, Janusz Marecki, and Thore Graepel. Multi-agent reinforcement learning in sequential social dilemmas. arXiv preprint arXiv: 2017.
Joel Z Leibo, Edgar A Duefezz-Guzman. Alexander Vezhnevets, John P Agapiou, Peter Sunehag, Raphael Koster, Jayd Matyas, Charlie Beattie, Igor Mordatch, and Thore Graepel. Scalable evaluation of multi-agent reinforcement learning with melting pot. In International Conference Machine Learning, pp. 6187-6199, PMLR, 2021.
Timothy Lillicrap, Jonathan Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. In International Conference on Learning Representations, 2016.
Michael I. Littman. Markov games as a framework for multi-agent reinforcement learning. In Machine learning proceedings 1994, pp. 157-163. Elsevier, 1994.
Ryan Lowe, Yi Wu, Aviv Tamar, Jean Harb, OpenAl Pieter Abbeel, and Igor Mordatch. Multi-agent actor-critic for mixed poperrative-copptttiii environments. In Advances in Neural Information Processing Systems, pp. 6390, 2017.
12

---

Published as a conference paper at ICLR 2023
Andrei Lupu, Brandon Cui, Hengyuan Hu, and Jakob Foerster. Trajectory diversity for zero-shot
coordination. In Interaatonaal Conference on Machine Learning, pp. 7204-7213, PMLR, 2021.
Clare Lyle, Mark Rowland, Will Dabney, Marta Kwiatkowska, and Yarin Gal. Learning dynamics and generalization in reinforcement learning. arXiv preprint arXiv:2206.02111 2022.
Anuj Mahajan, Mikayel Samvelyan, Tarun Gupta, Benjamin Ellis, Mingfei Sun, Tim Rocktäschel, and Shimon Whiteson. Generalization in cooperative multi-agent systems. arXiv preprint arXiv:2202.00104 2022.
Kevin R McKee, Joel Z. Leibo, Charlie Beattie, and Richard Everett. Quantifying the effects of environment and population diversity in multi-agent reinforcement learning, Autonomous Agents and Multi-Agent Systems, 36(1):1-16, 2022.
Andrew N Meltzoff, Patricia K Kuhl, Javier Movellan, and Terrence J Sejnowski. Foundations for new science of learning. science, 325(5938):284-28, 2009.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare G Bellemare, Alex Graves, Martin Riedmiller, Andreas Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. Nature, 5 518(7540):529 533, 2015.
Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lillicrap. Tim Harley, David Silver, and Koray Kavukcuoglu. Asynchronous methods for deep reinforcement learning. International conference on machine learning, pp. 1928-1937. PMLR, 2016
Philipp Moritz, Robert Nishihara, Stephanie Wang, Alexey Tumanov, Richard I Liaw, Eric Liang, Melih Elibol, Zongheng Yang, William Paul, Michael Jordan, al. Ray: A distributed framework for emerging {AI] applications. In 13th USENIX Symposium on Operating Systems Design and Implementation (OSDI 18), pp. 561-577, 2018.
Frans A Olichock, Matthijs TJ Spaan, and Nikos Vlassis. Optimal and approximate q-value functions for decentralized POMDPs. Journal of Artificial Intelligence Research, 32:289-353. 2008
Charles Packer, Katelyn Gao, Jernej Kos, Philipp Krähenbühl, Vladlen Koltun, and Dawn Song. Assessing generalization in deep reinforcement learning. arXiv preprint arXiv: /2282, 2018.
Georgios Papoudakis, Filippos Christianos, Lukas Schäfer, and Stefano V Albrecht. Benchmarking multi-agent deep reinforcement learning algorithms in cooperative tasks. Thirty-fithh Conference Neural Information Processing Systems Datasets and Benchmarks Track (Round 1), 2021.
Zhenghao Peng, Quanyi Li, Ka Ming Hui, Chunxiao Liu, and Bolei Zhou, Learning to simulate self-driven partieles system with coordinated policy optimization. Advances in Neural Information Processing Systems, 34: 10784-10777, 2021.
Julien Perolat, Bart de Vylder, Daniel Hennes, Eugene Tarassov, Florian Strub, Vincent de Boer, Paul Muller, Jerome Connor, Neil Burch, Thomas Anthony, et al. Mastering the game of stratego with model-free multiagent reinforcement learning. Science, 2022.
Wei Qiu, Weixun Wang, Rundong Wang, Bo An, Yujing Hu, Svetlana Obraztsova, Zinovi Rabinovich, Jianye Hao, Yingfeng Chen, and Changjie Fan. Off-beat multi-agent reinforcement learning. arXiv preprint 22Xiv:2205.131 2022.
Tabish Rashid, Mikayel Samvelyan, Christian Schroeder, Gregory Farquhar, Jakob Foerster, and Shi- mon Whiteson. QMIX: Monotonic value function factorisation for deep multi-agent reinforcement learning. International Conference on Machine Learning, pp. 4295-4304, 2018.
Tabish Rashid, Gregory Farquhar, Bei Peng, and Shimon Whiteson. Weighted qmix: Expanding monotonic value function factorisation for deep multi multi-agent reinforcement learning. Advances in Neural Information Processing Systems, 33:10199-102 2020.
John Schulman, Philipp Moritz, Sergey Levine, Michael Jordan, and Pieter Abbeel. High-dimensional continuous control using generalized advantage estimation. arXiv preprint arXiv:1506.00 02438, 2015.
13

---

Published as a conference paper at ICLR 2023
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347, 2017.
David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Mare Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, al. A general reinforcement learning algorithm that masters chess, shogi, and go through self-play. Science, 362(6419): 1140-1144, 2018.
Xingyou Song, Yiding Jiang, Stephen Tu, Yilun Du, and Behnam Neyshabur Observational overfitting in reinforcement learning. In International Conference on Learning Representations, 2019.
Peter Stone and Sarit Kraus. To teach or not teach?: decision making under uncertainty in ad hoc teams. In AAMAS, pp. 117-124, 2010.
Adam Stooke, Anuj Mahajan, Catarina Barros, Charlie Deck, Jakob Bauer, Jakub Sygnowski, Maja Trehacz, Max Jaderberg, Michael Mathieu, et Open-ended learning leads to generally capable agents. arXiv preprint 1rXiv:2107./2800 2021.
DJ Strouse, Kevin McKee, Matt Botvinick, Edward Hughes, and Richard Everett. Collaborating with humans without human data. Advances in Neural Information Processing Systems, 34: 14502-14515, 2021.
Robert Sugden. Rights, co-operation and welfare. The Economics of Rights, Co-operation and Welfare, pp. 170-182. Springer, 2005.
Richard S Sutton and Andrew G Barto. Reinforcement Learning: An Introduction. MIT press, 2018.
Richard S Sutton, Doina Precup, and Satinder Singh. Between mdps and semi-mdps: A framework for temporal abstraction in reinforcement learning. Artificial intelligence, 112(1-2):181-2111 1999.
Richard Stuart Sutton. Temporal credit assignment in reinforcement learning. PhD thesis, University of Massachusetts Amherst, 1984.
Ardi Tampuu, Tambet Matiisen, Dorian Kodelja, Ilya Kuzovkin, Kristjan Korjus, Juhan Aru, Jaan Aru, and Raul Vicente. Multiagent cooperation and competition with deep reinforcement learning. PLoS ONE, 12(4), 2017.
Zhenggang Tang, Chao Yu, Boyuan Chen, Huazhe Xu, Xiaolong Wang, Fei Fang, Simon Du Yu Wang, and Yi Wu. Discovering diverse multi-agent strategic behavior via reward randomization. arXiv preprint arXiv:2103.0456 2021.
Michael Tomasello. Origins of human communication. MIT press, 2010.
Alexander Vezhnevets, Yuhuai Wu, Maria Eckstein, Rémi Leblond, and Joel Z Leibo. Options as re- sponses: Grounding behavioural hierarchies in multi-agent reinforcement learning. In International Conference Machine Learning, pp. 9733 9942.. PMLR, 2020.
Oriol Vinyals, Igor Babuschkin, Wojciech M Czarnecki, Michaël Mathieu, Andrew Dudzik, Junyoung Chung, David H Choi, Richard Powell, Timo Ewalds, Petko Georgiev, et al. Grandmaster level in StarCraft using multi-agent reinforcement learning. Nature, 575(7782):350- -54,, 2019.
Jianhao Wang, Zhizhou Ren, Terry Liu, Yang Yu, and Chongjie Zhang. QPLEX: Duplex ducling multi-agent q-learning. In International Conference on Learning Representations, 2021a.
Weixun Wang, Jianye Hao, Yixi Wang, and Matthew Taylor. Towards cooperation in sequen- tial prisoner's s dilemmas: a deep multiagent reinforcement learning approach. arXiv preprint a0Xiv:1803.00162, 2018
Yihan Wang, Beining Han, Tonghan Wang, Heng Dong, and Chongjie Zhang. DOP: Off-policy multi-
agent decomposed policy gradients. In International Conference Learning Representations, 2021b.
Ronald J Williams.
Simple statistical gradient-followw algorithms for connectionist reinforcement learning. Machine learning, 8(3):229-256, 2566, 1992.
14

---

Published as a conference paper at ICLR 2023
Yaodong Yang and Jun Wang. An overview of multi-agent reinforcement learning from game theoretical perspective. arXiv preprint arXiv:2011.0058,, 2020.
Chao Yu, Akash Velu, Eugene Vinitsky, Yu Wang, Alexandre Bayen, and Yi Wu. The surprising 2021.
effectiveness of ppo in cooperative, multi-agent games. arXiv preprint
Lei Yuan, Jianhao Wang, Fuxiang Zhang, Chenghe Wang, ZongZhang Zhang, Yang Yu, and Chongjie Zhang. Multi-agent incentive communication via decentralized teammate modeling. Proceedings of the AAAI Conference on Artificial Intelligence, 36(9):9466 9474, Jun. 2022.
Daochen Zha, Wenye Ma, Lei Yuan, Xia Hu, and Ji Liu. Rank the episodes: A simple approach for
exploration in weweedurally-generatee environments. In International Conference Learning Representations, 2020.
Kaiqing Zhang, Zhuoran Yang, and Tamer Başar. Multi-agent reinforcement learning: A selective overview of theories and algorithms. Handbook of Reinforcement Learning and Control, pp. 321-384, 2021.
15


Reviews:
[{"review_id": "c14EtiXu1hE", "reviewer": "Reviewer_8Vwu", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "The authors propose a method for containing multiple distinct behaviours (or policies) in a single agent. To do this they store a dictionary of policies observed during training, where the key relates to returns observed during training (this is discretised to keep the buffer size reasonable). \n\nThis is actually very similar to simply holding a population of agents during training. At the start of training the dictionary (size N)  is initialised with N random policies which are all selected randomly and trained with. RPM uses self-play from its buffer to train more agents. Unlike self-play or population-play their is no risk of degeneracy as values are only overwritten for agents which produce the same return.", "summary_of_the_review": "Simple method but paper lacks clarity.\n\n", "strength_and_weaknesses": "### Strengths\n\n* Idea is simple and good first step in the melting pot game\n* Good ablations\n\n\n### Weaknesses\n* No explanation of the RPM update rule.\n* Method makes a major assumption that return is enough to distinguish behaviour. A toy example of where this fails would be that grim trigger and tit-for-tat would get similar returns in IPD against a defective agent but intuitively have some variance in behaviour (e.g.  tit-for-tat is forgiving but grim trigger is not)\n* Unclear how large a RPM buffer should be\n* This method is computationally much more intensive than baselines, some analysis to count the different number of timesteps used in training or when convergence is achieved would also be reasonable.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "_iwsEjiDem", "reviewer": "Reviewer_7r99", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_paper": "This paper proposes a simple method called ranked policy memory (RPM) that can be plugged in any existing MARL algorithms to solve the generalization problem of MARL. The main idea of RPM is maintaining a look-up memory of the history rollout policies which are ranked by the training episode return. At each episode, the rollout policies are uniformly sampled from RPM. The objective of this process is to keep the diversity of agents' policies and resemble the the unknown policies that may appear in the evaluation scenarios. The performance of RPM is empirically verified by experiments and abnalation studies.", "summary_of_the_review": "The proposed method in this paper performs better than the baselines and it is demonstrated in the ablation study that it should be effective. Nevertheless, the principle of the effectiveness is blurry.", "strength_and_weaknesses": "## Strength\n1. This paper is generally well written and the description of the proposed method is clear.\n2. The motviation of this paper is clear and I believe this is a meaningful work.\n3. The proposed method is demonstrated to improve the performance of generalization.\n4. The ablation study well spots the limitation of the proposed method, so that it is transparent and easy for the followers to improve it.\n5. The comparisons to the prior works are sufficient.\n\n## Weaknesses\n1. The proposed method is so heuristic (though it cannot be a reason to reject it), so that it is unclear why it works.\n2. Although the authors claim that the diversified multi-agent trajectories can resemble trajectories generated by the interaction with agents possessing unknown policies in the evaluation scenario, this explanation is unconvincing to me. The most critical reason is that the background agent is pre-trained, so it is possible that the policy space of trained agents **completely** deviates from the policy space of pre-trained agents (with no intersection). The authors should give a better explanation.\n3. The proposed RPM is highly dependent on the choice of a hyperparameter $\\psi$ as shown in ablation study. Could the authors give a brief proposal to address this issue?\n4. As shwon in Fig. (e) in ablation study, the mode of the final distribution of keys of RPM is almost the mean of returns. It can be estimated that the effect of RPM could make the MARL policies adapt the average performance. This might lead to the issue as the authors discussed in the paper that MARL agents' performances will affect the evaluation performance.", "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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "CiOP36PeQC1", "reviewer": "Reviewer_GwoH", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes a new self-play training framework called RPM that focuses on the diversity of the multi-agent population. Specifically, RPM builds the population by maintaining various levels of policies via ranking. Then, RPM trains focal agents that behave well with background agents sampled from the population. The extensive evaluations based on the melting pot domain show the generalization of RPM when interacting with unseen agents in the evaluation scenarios. ", "summary_of_the_review": "Overall, I have a positive evaluation of this paper (score of 6), and I will make a final decision on the recommendation after the authors' response.", "strength_and_weaknesses": "**Strengths:**\n1. The paper is generally well-written and conveys the methods clearly. The figures are also helpful in understanding the method.\n2. While RPM is a relatively simple algorithm based on the episodic return ranking system, it shows effectiveness in multiple scenarios. As such, the algorithm is directly applicable to other settings/methods.\n\n**Questions:**\n1. The problem formation and objective in Section 3 are closely related to meta-learning in MARL (Al-Shevidat et al., ICLR 2018; Kim et al., ICML 2021), where the goal is to train a meta-agent with a population of other agents such that the meta-agent can adapt well when interacting with a new agent at meta-testing. The main difference between this paper and meta-MARL is that the focal agents are not allowed to fine-tune their policies during the evaluation in this paper, while meta-agents are allowed to fine-tune their policies. Because both settings are concerned with generalization, I would like to ask discussion comparing the two settings. \n2. Would RPM benefit from using more complicated ranking systems (e.g., TrueSkill)?\n3. Adding lines that denote optimal values in Figure 6 (i.e., if ideal generalization is possible) can help identify the gap and the amount of generalization performed by RPM.  \n\n**References:**  \n* Maruan Al-Shedivat, Trapit Bansal, Yuri Burda, Ilya Sutskever, Igor Mordatch, Pieter Abbeel. Continuous Adaptation via Meta-Learning in Nonstationary and Competitive Environments. ICLR 2018   \n* Dong-Ki Kim, Miao Liu, Matthew Riemer, Chuangchuang Sun, Marwa Abdulhai, Golnaz Habibi, Sebastian Lopez-Cot, Gerald Tesauro, Jonathan P. How. A Policy Gradient Algorithm for Learning to Learn in Multiagent Reinforcement Learning. ICML 2021", "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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "Aho-Z5D9Gf", "reviewer": "Reviewer_3kor", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper considers improving the generalization capability of MARL agents. The idea is to maintain an archive of policies based on their discretized returns. In each episode, agents from random return categories are selected to perform RL training, which ensures that each episode can contain diversified agent interactions. Experiments are conducted on the melting pot environment against a collection of baselines.\n\nAlthough the idea of using policies of different skill levels for improved generalization isn't new in MARL, the execution of this idea in the setting of general multi-agent games is neat and intuitive. \n\n\n+++++++++++++++++++++++ post rebuttal +++++++++++++++++++++++\nThe authors have included additional results on the baselines, which makes the paper more compete. Therefore, I decided to update my score from 5 to 6. \n", "summary_of_the_review": "This is a well-written paper with a neat idea. The current content is very close to the bar of acceptance in my opinion and can be further improved if more in-depth analysis can be provided. ", "strength_and_weaknesses": "## Strength\n\nThe paper is clearly written and easy to follow. Although the overall idea isn't groundbreaking, it is still novel to store policies in a discretized memory and perform training over randomly sampled policies. This is algorithmically different from the classical way of using policy archives in MARL, which typically follows the framework of fictitious self-play. In addition, the selected testbed is sufficiently challenging. The proposed method could be well served as a baseline for the following works. \n\n## Weakness\n\n### Missing citations\n\nIn the related work section, the authors claim that \"_there is no method proposed to achieve generalization in MARL_\", which, to the best of my knowledge, is not true. It is true that there isn't a systematic study on the setting of general sum and more than two agents, but there are indeed a lot of works on relatively more narrow domains. For example, [1] adopts the same idea of using past policies to generate diverse interactions so that the learned policy can generalize to humans. The difference is that [1] conducts two stages: i.e.,  first, create a policy population of different skill levels and then train an adaptive policy from scratch to compete with diverse partners so that it can generalize during evaluation. [2] also considers the stag hunt game and follows a similar training paradigm to [1] to train a policy that can adapt to cooperative or non-cooperative partners. [3] adopts a similar population-based training framework to this work but improves the generalization ability of policies by promoting policy diversity. I think the paper should also carefully discuss these related works in the paper. \n\n[1] Collaborating with Humans without Human Data, DJ Strouse, Kevin R. McKee, Matt Botvinick, Edward Hughes, Richard Everett, NeurIPS 2021. \n\n[2] Discovering Diverse Multi-Agent Strategic Behavior via Reward Randomization, Zhenggang Tang, Chao Yu, Boyuan Chen, Huazhe Xu, Xiaolong Wang, Fei Fang, Simon Shaolei Du, Yu Wang, Yi Wu, ICLR 2021\n\n[3] Trajectory Diversity for Zero-Shot Coordination, Andrei Lupu, Brandon Cui, Hengyuan Hu, Jakob Foerster, ICML 2021\n\n### Relationship to Fictitious Self-Play (FSP)\nI have been carrying by the same question throughout the reading of this paper. Although I do see experiments between the proposed method and FSP, I could still hardly understand **why** (at least intuitively) FSP is worse than RPM. I think the paper can be much improved if this question can be carefully answered and discussed. Some of my thoughts on this question are listed below.\n\n1. **The performance of FSP should be tuned**. In Fig 6, the performance of HSP is substantially worse than MAPPO and it is even worse than _random_. I checked the appendix, which states that HSP uses a surprisingly high past sampling rate of 30%. Particularly in the case of multiple agents, such a hyper-parameter choice could largely hurt MARL training. As a reference, [4] uses a 5% past sampling rate. I do think this hyper-parameter should be carefully tuned to ensure a fair comparison, considering the fact that FSP is perhaps the most important baseline to compare with. In particular, the RPM-random baseline achieves comparable performance to RPM in the prisoner's dilemma game while FSP is even worse than random. \n\n\n[4] Emergent Tool Use From Multi-Agent Autocurricula, Bowen Baker, Ingmar Kanitscheider, Todor Markov, Yi Wu, Glenn Powell, Bob McGrew, Igor Mordatch, ICLR 2020\n\n2. **The motivation for using a discretized category (rank)**. I'm definitely convinced that we should run MARL training with partners with different skill levels. And, it is great to see in the ablation studies that RPM-random baseline works worse. However, I don't think the paper at any place **explains** and **motivates** why the use of a discretized rank is _necessary_. Intuitively, why wouldn't past sampling achieve the same effect? Note that RPM-random is indeed comparable to RPM in the prisoner's dilemma case. By contrast, why does RPM-random works poorly in pure cooperation? Note that random sampling achieves strong performances in the overcooked game [1], which is also a purely cooperative game. I do think some in-depth analysis should be conducted. \nA possible reason that I can imagine is as follows. Based on the histogram in fig 8(e), the distribution of policy skill levels is not uniform. Those high-reward policies are much rarer than sub-optimal ones. So a naive random sampling may hardly choose those high-reward policies, which accordingly makes training slow. This could be a fair argument. However, if we exclude those policies with the highest rewards (e.g., return > 10), those sub-optimal policies are distributed pretty much uniformly in fig.8(e) to some extent.  So, couldn't this issue (uneven distribution of skill levels) be just solved by FSP with a properly tuned past sampling rate? With a properly tuned rate, the probability of choosing a recent high-reward policy and choosing a poor past policy can be well balanced, if fig 8(e) is a generic diagram for most MARL applications. So, in addition to tuning the FSP baseline better, I would suggest the authors study the policy distribution over every scenario to have a better **understanding** of why random sampling would fail and why a discretized category is necessary. \n\n3. **A fair comparison**. This is a final and possibly repetitive comment. RPM requires careful tuning over the value of $\\phi$, and RPM would simply generate RPM-random if $\\phi$ approaches 0. Unfortunately, there isn't a generic way to choose a good $\\phi$ (at least not in the current draft), so I would believe a similar amount of tuning efforts should be made for FSP on past sampling rates for a fair comparison. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "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": {}}]

Author rebuttal:

Decision: Accept: poster