Discovering Diverse Multi-Agent Strategic Behavior via Reward Randomization
Authors: Zhenggang Tang
Chao Yu
Boyuan Chen
Huazhe Xu
Xiaolong Wang
Fei Fang
Simon Shaolei Du
Yu Wang
Yi Wu
Venue: ICLR 2021 Poster (2021)
Keywords: strategic behavior
multi-agent reinforcement learning
reward randomization
diverse strategies

Abstract: We propose a simple, general and effective technique, Reward Randomization for discovering diverse strategic policies in complex multi-agent games. Combining reward randomization and policy gradient, we derive a new algorithm, Reward-Randomized Policy Gradient (RPG). RPG is able to discover a set of multiple distinctive human-interpretable strategies in challenging temporal trust dilemmas, including grid-world games and a real-world game Agar.io, where multiple equilibria exist but standard multi-agent policy gradient algorithms always converge to a fixed one with a sub-optimal payoff for every player even using state-of-the-art exploration techniques. Furthermore, with the set of diverse strategies from RPG, we can (1) achieve higher payoffs by fine-tuning the best policy from the set; and (2) obtain an adaptive agent by using this set of strategies as its training opponents. 

Published as a conference paper at ICLR 2021
DISCOVERING DIVERSE MULTI-AGENT STRATEGIC BEHAVIOR VIA REWARD RANDOMIZATION
Zhenggang Tang" let, Chao Yu" Boyuan Chen?, Huazhe Xu², Xiaolong Wang', Fei Fang', Simon Du?, Yu Wang', Yi Wu 12: Tsinghua University. 2 Shanghai Qi Zhi Institute, UC Berkeley, UCSD, CMU,
6 Peking University, University of Washington
# zoeyuchao@gmail.
com, com,
com com
ABSTRACT
We propose a simple, general and effective technique, Reward Randomization for discovering diverse strategic policies in complex multi-agent games. Combining reward randomization and policy gradient, we derive a new algorithm, Reward- Randomized Policy Gradient (RPG). RPG is able to discover multiple distinctive human-interpretable strategies in challenging temporal trust dilemmas, including grid-world games and a real-world game Agazio, where multiple equilibria exist but standard multi-agent policy gradient algorithms always converge to fixed with a sub-optimal payoff for every player even using state-of-the-arr exploration techniques. Furthermore, with the set of diverse strategies from RPG, we can (1) achieve higher payoff's by fine-tuning the best policy from the set; and (2) obtain an adaptive agent by using this set of strategies as its training opponents. The source code and example videos can be found in our website: https:/ /sttee////ttssseeeeeeeeeeeeeeees wwt.ssitogsillia.oooooooo [com/ eew staghuntrpo
INTRODUCTION
Games have been long-standing benchmark for artificial intelligence, which prompts persistent technical advances towards our ultimate goal of building intelligent agents like humans, from Shannon's 's initial interest in Chess (Shannon 1950) and IBM DeepBlue (Campbell et al. 2002). to the most recent deep reinforcement learning breakthroughs in Go (Silver et al.) 2017). Dota II (OpenAl et al. 2019) and Starcraft (Vinyals et al. 2019). Hence, analyzing and understanding the challenges in various games also become critical for developing new learning algorithms for even harder challenges.
Most recent successes in games are based on decentralized multi-agent learning (Brown 1951 Singh al. 2000 Lowe al. 2017 Silver et al., 2018), where agents compete against each other and optimize their own rewards to gradually improve their strategies. In this framework, Nash Equilibrium (NE) (Nash 195T), where
player could benefit from altering its strategy unilaterally, provides a general solution concept and serves as a goal for policy learning and has attracted increasingly
significant interests from Al researchers (Heinrich & Silver 2016 Lanctot al. 2017 Foerster et al.)
2018; Kamra et al., 2019 Han & Hu/ 2019] Bai & Jin 2020) Perolat et al. 20200: many existing
works studied how to design practical multi-agent reinforcement learning (MARL) algorithms that can provably converge to an NE in Markov games, particularly in the zero-sum setting.
Despite the empirical success of these algorithms, fundamental question remains largely unstudied in the field: even if an MARL algorithm converges to an NE, which equilibrium will converge to? The existence of multiple NEs is extremely common in many multi-agent games. Discovering as many NE strategies as possible particularly important in practice not only because different NEs can produce drastically different payoffss but also because when facing unknown players who are trained to play an NE strategy, we can gain advantage by identifying which NE strategy the opponent is playing and choosing the most appropriate response. Unfortunately. in many games where multiple distinct NEs exist, the popular decentralized policy gradient algorithm (PG), which has led to great successes in numerous games including Dota II and Stacraft, always converge to particular NE with non-optimal payoffs and fail to explore more diverse modes in the strategy space.
Consider an extremely simple example, a 2-by-2 matrix game Stag- (Rousseau) 1984 Skyrms 2004), where two pure strategy NEs exist: a "risky" cooperative equilibrium with the highest payoff
Equual contribution. Work done intern at Institute for Interdisciplinary Information Sciences (IIIS). Tsinghua University.

---

Published as a conference paper at ICLR 2021
for both agents and "safe" non-cooperative equilibrium with strictly lower payoffs. We show, from both theoretical and practical perspectives, that even in this simple matrix-form game, PG fails to discover the high-payoff "risky" NE with high probability. The intuition is that the neighborhood that makes policies converge to the "risky" NE can be substantially small comparing to the entire policy space. Therefore, an exponentially large number of exploration steps are needed to ensure PG discovers the desired mode. We propose a simple technique, Reward Randomization (RR), which can help PG discover the "risky" cooperation strategy in the stag-hunt game with theoretical guar- antees. The core idea of RR is to directly perturb the reward structure of the multi-agent game of inter- est, which is typically fow-dimensional. RR directly alters the landscape of different strategy modes in the policy space and therefore makes it possible to easily discover novel behavior in the perturbed game (Fig. D.
risky coop.
evaluate in the orignal game
coop:
no0-000p.
candomization
non-coop.
policy space
policy space
Hunt
Perturbed Game
Figure 1: Intuition of Reward Randomization
We call this new PG variant Reward-Randoninn Randomized Policy Gradiens (RPG).
To further illustrate the effectiveness of RPG, we introduce three Markov games two gridworld games and a real-world online game Agario All these games have multiple NEs including both "risky" cooperation strategies and "safe" non-cooperative strategies. We empirically show that even with state-of-the-an exploration techniques, PG fails to discover the "risky" cooperation strategies. In contrast, RPG discovers a surprisingly diverse set of human- humman-nterppettbble strategies in all these games, including some non-trivial emergent behavior. Importantly, among this set are policies achieving much higher payoffss for each player compared to those found by PG. This "diversity- seeking" property of RPG also makes feasible to build adaptive policies: by re-training an RL agent against the diverse opponents discovered by RPG, the agent is able to dynamically alter its strategy between different modes, e.g., either cooperate or compete, w.r.f. its test-time opponent's behavior.
We summarize our contributions as follow
We studied a collection of challenging multi-agent games, where the popular multi-agent PG algorithm always converges to sub-optimal equilibrium strategy with low payoff's.
A novel reward-space exploration technique, reward randomization (RR), for discovering hard-to-find equilibrium with high payoffs. Both theoretical and empirical results show that reward randomization substantially outperforms classical policy/action-spee space exploration techniques in challenging trust dilemmas.
We empirically show that RR discovers surprisingly diverse strategic behaviors in complex Markov games, which further provides a practical solution for building an adaptive agent.
A new multi-agent environment Agario, which allows complex multi-agent strategic behavior. We released the environment to the community as a novel testbed for MARL research.
2 A MOTIVATING EXAMPLE: STAG HUNT
We start by analyzing a simple problem: finding the NE with the optimal payoffs in the Stag Hunt game. This game was originally introduced in Rousseau's 's work, "A discourse of hunters are tracking a big stag silently: now a hare shows up, each hunter should decide whether to keep tracking the stag or kill the hare immediately. This leads to the 2-by-2 matrix- foom stag-hum game in Tab. with two actions for each agent, Stag (S) and Hare (H). There are two pure strategy NEs: the Stag NE, where both agents choose and receive a high payoff a (c.g., a = 4), and the Hare NE, where both agents choose H and receive lower payoff d (e.g., d = 1). The Stag NE is "risky" because if one agent defects, they still receives a decent reward (e.g., b = 3) for eating the hare alone while the other agent with an S action may suffer from big loss for being hungry (e.g.,
Stag
Hare
Stag
a, a
C, d, d
inequality" (Rousseau 1984;: group
Hare
b, c
Table 1: The stag-hunt
game, a > b > d > c.
10))
Formally, let A [S. denote the action space. ( denote the policy for agent i (i E {1, 2)) parameterized by 0g, i.e., (l,,(O,) = S] = O2 and (0,) = H] 1- 0,, and R(a1, (2; denote the payoff for agent i when agent 1 takes action @i and agent 2 takes action d2. Each agent optimizes its expected utility (T),,, 72) = Ea [R(a), az; i)). Using the standard policy gradient algorithm, typical learning procedure is to repeatedly take the following two steps until
2

---

Published as a conference paper at ICLR 2021
convergencd (1) estimate gradient V, ( T2) via self-play; (2) update the policies by 0g 4 02 + aV; with learning rate a. Although PG is widely used in practice, the following theorem shows in certain scenarios, unfortunately, the probability that PG converges to the Stag NE is low.
Theorem 1. Suppose a - b = e(d c) for some 0 < E < 1 and initialize 01, 82 ~ Unif [o, 1]. Then
the probability that PG discovers the high-payoff NE is upper bounded by 2c4r2
142c+e2
Theorem 1 shows when the risk is high (i.e., e is low), then the probability of finding the Stag NE via PG is very low. Note this theorem applies to random initialization, which standard in RL.
Remark: One needs at least N = 2 (2) restarts to ensure a constant success probability.
Fig. 2 shows empirical studies: we select 4 value assignments, i.c., E
100
{-5, 20, -00 - } and a=4, b=3, d=1, and run a state-of-the-at PG method, proximal policy optimization (PPO) (Schulman et al.) 2017), these games. The Stag NE is rarely reached, and, as e becomes smaller, the probability of finding the Stag NE significantly decreases. PPeysakhovich & Lerer (2018b) provided a theorem of similar flavor without analyzing the dynamics of the learning algorithm whereas we explicitly characterize the behavior of PG. They studied a prosocial reward- reward-sharing scheme, which transforms the reward of both agents to R(a1, 02; +)+ +) az: 2). Reward sharing can be viewed as a special case of our method and, as shown in Sec. [ it is insufficient for solving complex temporal games.
eounbbau bas
Ca:5
Epiondes
Figure 2: PPO in stag hunt, with a=4, b=3, d=1 and various e (10 seeds).
2.1 REWARD RANDOMIZATION IN THE MATRIX-FORM STAG-HUNT GAME
9 Thm. [ suggests that the utility function R highly influences what strategy PG might learn. Taking one step further, even if a strategy is difficult to learn with a particular R, it might be casier in some other function Rt. Hence, if we can define an appropriate space R over different utility functions and draw samples from R. we may possibly discover desired novel strategies by running PG on some sampled utility function R' and evaluating the obtained policy profile on the original game with R. We call this procedure Reward Randomization (RR).
Concretely, in the stag-hunt game, Rt is parameterized by 4 variables (aR, bR, CR. dR). We can define distribution over Rd, draw tuple It' (aR', bR: CR', , dx) from this distribution, and run PG on R'. Denote the original stag-hunt game where the Stag NE is hard to discover as Ro. Reward randomization draws N perturbed tuples RI,..., RN. runs PG on each R., and evaluates each of the obtained strategies on Ro. The theorem below shows is highly likely that the population of the N policy profiles obtained from the perturbed games contains the Stag NE strategy.
Theorem 2. For any Stag-Hunt game, suppose in the i-th run of RR we randomly generate an,, bn, CR. dn, ~ Unif [-1, 1] and initialize 01, 02 ~ Unif [0, 1). then with probability at least 1 1-6.6 = 1 exp (-Ω (N)), the aforementioned RR procedure discovers the high-payoff NE.
Here we use the uniform distribution as an example. Other distributions may also help in practice. Comparing Thm. and Thm.[]
[ RR significantly improves standard PG w.r.t. success probability.
Remark 1: For the scenario studied in Thm. to achieve a (1 11 8) success probability for some 0 <<8 < 1, PG requires least N S2 ( log (t)) random restarts. For the same scenario, RR only requires to repeat at most N = O (log (1/8)) which is independent of When is small, this is a huge improvement.
Remark 2: Thm. [ suggesss that comparing with policy randomization, perturbing the payoff matrix makes it substantially easier to discover a strategy that can be hardly reached in the original game.
Note that although in Stag Hunt, we particularly focus on the Stag NE that has the highest payoff for both agents, in general RR can also be applied to NE selection in other matrix-form games using payoff evaluation function E(TI,T2) for a prosocial NE, look for Pareto-optimal NEs by setting E(TI, 22) 30 (TI, (3)2 (TI, R2) with 0 < B < 1.
For example, we can set E(TI, T2) = Un (TT, 72) U2 (TI, T2)
( T2) +
In general matrix games heyond stag hunt, the procedure can be eyclic as well (iighh 2000
3

---

Published as a conference paper at ICLR 2021
Algorithm 1: RPG: Reward- Randomized Policy Gradient
Input: original game M, search space R. evaluation function E, population size N:
draw samples { ( R from R:
(#] (1) 222 } PG induced games {M(R())) in parallet; ; (9) (0)
// RR phase
(k) (k) by k = arg max; E(Ti T2 20)// ;// evaluation phase
select the best candidate m1 "T2
(k) =7(4)) on M via PG (if necessary);
of. 22 < fine-tune 71 : x2
// fine-tuning phase
return Ti, m2;
3 RPG:
POLICY GRADIENT
Herein, we extend Reward Randomization to general multi-agent Markov games. We now utilize RL terminologies and consider the 2-player setting for simplicity. Extension to more agents is straightforward (Appx. B.3
Consider a 2-agent Markov game M defined by (S,0,A, R, P), where S is the state space; O for : 8 E S, 0: = O(s, i), E {1,2)} is the observation space, where agent receives its own observation 0; (s; (in the fully observable setting, O(s, i) 8); A is the action space for each agent; R(s, 01, 42; i) is the reward function for agent i; and P( |s, 01 a2) is transition probability from state to state s' when agent takes action dg. Each agent has a policy [o;; 02) which produces a (stochastic) action and is parameterized by 0g. In the decentralized RL framework, each agent i optimizes its expected accumulative reward (0:) Eay 221 [ R(s", dj. al; i)] with some discounted factor 7.
Consider we run decentralized RL on a particular Markov game M and the derived policy profile is (01), nz (f2)). The desired result is that the expected reward (8,) for each agent is maximized. We formally written this equilibrium evaluation objective as an evaluation function E T2) and therefore the goal to find the optimal policy profile (T x²) w.r.t. E. Particularly for the games we considered in this paper, since every (approximate) equilibrium we ever discovered has symmetric payoff, we focus on the empirical performance while assume a much simplified equilibrium selection problem here: it is equivalent to define F T2) by F( T2) = 3UU, (0,) + (1 U2U2((s) for any 0 S B 1. Further discussions on the general equilibrium selection problem can be found in Sec. [
The challenge is that although running decentralized PG is a popular learning approach for complex Markov games, the derived policy profile (T1, T2) is often sub-optimal, i.e., there exists (Mj, m²) such that E(Ti, m²) ) > E(T π2). It will be shown in Sec. that even using state-of-the-arr exploration techniques, the optimal policies (xi. mT) can be hardly achieved.
Following the insights from Sec. [ reward randomization can be applied to a Markov game M similarly: if the reward function in M poses difficulties for PG to discover some particular strategy, it might be casier to reach this desired strategy with a perturbed reward function. Hence, we can then define a reward function space R. train a population of policy profiles in parallel with sampled reward functions from R and select the desired strategy by evaluating the obtained policy profiles in the original game M. Formally, instead of purely learning in the original game M = (S, O, R, P). we define a proper subspace R. over possible reward functions R S x A x A + R and use (RR) = (S, A, Rt, P)) to denote the induced Markov game by replacing the original reward function R with another R2' E R. To apply reward randomization, we draw N samples R!())..., R(N)
from R. run PG to learn (z( mT2)
(f)) each induced game M (1)(0)) and pick the desired policy (k) (k)) by calculating E in the original game M. Lastly, we can fine-tune the policies profile (IT
Ti m22 in M to further boost the practical performance (see discussion below). We call this learning procedure,
(As) (R)
Policy Gradient (RPG), which is summarized in Algo. [
Reward-function space: In general, the possible space for valid reward function is intractably huge. However, in practice, almost all the games designed by human have low-dimensional reward structures based on objects or events, so that we can (almost) always formulate the reward function in a linear form R(s, a1, 0z; i) = ((s, 01 02; i)T where Φ(s, 01 0z; i) is a low-dimensional feature vector and to is some weight.
simple and general design principle for R is to fix the feature vector é while only randomize the weight w, i.e., R = (Rw (8, 41, az; = ø(s, 01 i) w, ||w]] < )_ Hence, the overall search space remains similar structure as the original game M but contains diverse range of preferences over different feature dimensions. Notably, since the optimal strategy is invariant to the scale of the reward function R, theoretically any Crax > 0 results in the same search space.
4

---

Published as a conference paper at ICLR 2021
However, in practice, the scale of reward may significantly influence MARL training stability, typically ensure the chosen Cmax to be compatible with the PG algorithm in use.
Note that feature-hased reward function is standard assumption in the literature of inverse RI. Ng jet al. 2000, Ziebart et al.
2008: Hadfield-Menell et al., 2017). In addition, such reward structure is
also common in many popular RL. application domains. For example, in navigation games (Mirowski 2018). the reward is typically set to the negative distance from the target location LT to the agent's location LA plus a success bonus, so the feature vector (5s, a) can be written as a 2-dimensional vector LT LA LAll2. [LL LA]]:
al. 2016 Lowe et al. 2017; Wu al.
]] in real-time strategy games (Wu & Tian 2016; Vinyals et al. 2017] OpenAl ct al. 2019). e is typically related to the
bonus points for destroying each type of units; in robotics manipulation (Levine et al., 2016 [i et al. 2020 Yu et al. 2019). Φ is often about the distance between the robot/object and its target position; in general multi-agent games (Lowe et al. each agent's 's individual reward as well as the joint reward over each team, which also enables the representation of different prosociality levels for the agents by varying the weight w.
2017 Leibo et al. 2017 Baker et al.) 2020), , could contain
There are two benefits: (1) the policies found in the perturbed game may not remain an equilibrium in the original game, so fine-tuning ensures convergence; (2) in practice, fine-tuning could further help escape a suboptimal mode via the noise in PG (Ge et al. 2015 Kleinberg et al. 2018). We remark that practical issue for fine-tuning is that when the PG algorithm adopts the actor-critic framework (e.g., PPO), we need an additional critic warm-start phase, which only trains the value function while keeps the policy unchanged, before the fine-tuning phase starts. This warm-start phase significantly stabilizes policy learning by ensuring the value function is fully functional for variance reduction w.r.t. the reward function R in the original game M when estimating policy gradients.
Fine tuning:
3.1 LEARNING TO ADAPT WITH DIVERSE OPPONENTS
In addition to the final policies ii. Tे. another benefit from RPG is that the population of N policy profiles contains diverse strategies (more in Sec. (). With a diverse set of strategies, we can build an adaptive agent by training with random opponent policy sampled from the set per episode, so that the agent is forced to behave differrnnlyy based on its opponent's 's behavior. For simplicity, we consider learning an adaptive policy xf for agent 1. The procedure
Algorithm 2:
Learning to Adapt
Input: game M, policy set II,, initial nf; repeat
draw a policy vh from ll;;
evaluate лं and m2 M and collect data; update 8 via PG if enough data collected; until enough iterations;
return Ti Ti")::
remains the same for agent 2. Suppose a policy population P (
(N) } obtained during m2
the RR phase, we first construct diverse strategy set II, C P that contains all the discovered behaviors from P. Then we construct mixed strategy by randomly sampling a policy ny from IT2 in every training episode and run PG to learn πî by competing against this constructed mixed strategy. The procedure is summarized in Algo. 2 Note that setting IT, = P appears to be a simple and natural choice. However, in practice, since 'P typically contains just few strategic behaviors, it is unnecessary for 11, to include every individual policy from P. Instead, it sufficient to simply ensure 1ll contains at least one policy from each equilibrium in P (more details in Sec. 5.3). Additionally, this method does not apply the one-shot game setting (i.e., horizon is 1) because the adaptive agent does not have any prior knowledge about its opponent's 's identity before the game starts.
Implementation: We train an RNN policy for 7 (8*). It is critical that the policy input does not directly reveal the opponent's 's identity, so that it is forced to identify the opponent strategy through what it has observed. On the contrary, when adopting an actor-critic PG framework (Lowe et al.) 2017). it is extremely beneficial to include the identity information in the critic input, which makes critic learning substantially easier and significantly stabilizes training. We also utilize multi-head architecture adapted from the multi-task learning literature (Yu et al., 2019). i.e., use a separate value head for each training opponent, which empirically results in the best training performance.
4 TESTBEDS FOR RPG: TEMPORAL TRUST DILEMMAS
We introduce three 2-player Markov games as testbeds for RPG. All these games have a diverse range of NE strategies including both "risky" cooperative NEs with high payoffs but hard to discover and "safe" non-cooperative NES with lower payoffs. We call them temporal trust dilemmas. Game descriptions are in a high level to highlight the game dynamics. More details are in Sec. and App. B
5

---

Published as a conference paper at ICLR 2021
Gridworlds: We consider two games adapted from Peysakhovich & Lerer (2018b), Monster- Hunt
(Fig. 3 and Escalation (Fig. D. Both games have a 5-by-5 grid and symmetric rewards.
Monster-Hunl contains monster and two apples. Apples are static while the monster keeps moving towards its closest agent. If single agent meets the monster, it loses penalty of 2; if two agents catch the monster together, they both earn bonus of 5. Eating an apple always raises bonus of 2. Whenever an apple is caten or the monster meets an agent, the entity will respawn randomly. The optimal payoff can only be achieved when both agents precisely catch the monster simultancously.
Aguuss
Apple
Agui2
+2
Masta
Figure 3: Monster-Humm
Escalation contains lit grid. When two agents both step the lit grid, they both get a bonus timestep. If only one agent steps the lit grid, it gets penalty of 0.9L, where denotes the consecutive cooperation steps until that timestep, and the lit grid will respawn randomly. Agents need to stay together the lit grid to achieve the maximum payoff despite of the growing penalty. There are multiple NEs: for each I., that both agents cooperate for I. steps and then leave the lit grid jointly forms an NE.
and a neighboring grid will be lit up in the next
gight
Aspant
Figure 4: Escalation
Agar.io io is popular multiplayer online game. Players control cells in Petri dish to gain as much mass as possible by eating smaller cells while avoiding being eaten by larger ones. Larger cells move slower. Each player starts with one cell but can split sufficiently large cell into two, allowing them control multiple cells (Wikipedia) 2020 We consider simplified scenario (Fig. 5 with players (agents) and tiny script cells, which automatically runs away when an agent comes by. There is low-risk non-cooperative strategy, i.e., two agents stay away from each other and hunt script cells independently. Since the script cells move faster, it challenging for a single agent to hunt them. By contrast, two agents cooperate to encircle the script cells to accelerate hunting. However, cooperation is extremely risky for the agent with less mass: two agents need to stay close to cooperate but the larger agent may defect by eating the smaller one and gaining immediate big bonus.
Sccipt (fied)
Scrppt Cill
+Skant +Stzae
Aguu
sbibel -Prrolly(s)
Serige Call
Hant
+Sbzx( )
Agpedi
Persilt(
(a) Basic elements
(b) Common behavior: Split, Hunt and Merge
Figure 5: Agario: (a) simplified 2-player setting; (b) basic motions: split, hunt script cells, merge.
5 EXPERIMENT RESULTS
In this section, we present empirical results showing that in all the introduced testbeds, including the real-world game Agar.io, RPG always discovers diverse strategic behaviors and achieves an equilibrium with substantially higher rewards than standard multi-agent PG methods. We use PPO (Schulman al. 2017) for PG training. Training episodes for RPG are accumulated over all the perturbed games. Evaluation results are averaged over 100 episodes in gridworlds and 1000 episodes in Agario. We repeat all the experiments with 3 seeds and use X(Y) denote mean X with standard deviation Y in all tables. Since all our discovered (approximate) NEs are symmetric for both players, evaluation function and only measure the reward of
simply take E(T1, x2) = (TT T2) agent in all experiments for simplicity. More details can be found in appendix.
5.1 GRIDWORLD GAMES
Wermsten
Feadustr
Monster-Hunt: Each agent's reward is determined by three features per timestep: (1) whether two agents catch the monster together; (2) whether the agent steps on an apple; (3) whether the agent meets the monster alone. Hence, we write ő(s, 41, a2; i) a 3-dimensional 0/1 vector with one dimension for one feature. The original game corresponds to w = 5,, 2, 2].. We set Cnax = 5 for sampling w.
Rosats
RS-CNT
70
17U
We compare RPG with a collection of baselines, including standard PG (PG), PG with shared reward (PG+SR), population-basse -based training (PBT), which trains the same amount of parallel PG policies RPG,
Figure 6: Full process of RPG in Monster-Hunt

---

Published as a conference paper at ICLR 2021
Monster moves towards the closest agent
Chase grnti
Reqawn
Move together
logether
Stay one grid and wait for Slog Respame
Two agenits stop on the same grid. Respawn
C Chase A geat
(a) Strategy w. w=[5, O, 0] and w=|5, 0, 2] (hy chance)
(b) The final strategy after fine-tuning
Figure 7: Emergent cooperative (approximate) NE strategies found by RPG in Monster-HHum
Cel
Class to other
Eat
PBT
RR
RPG
RND
Rew. 3,8(0.3)
3.8(0.2)
4,3(
2.8(0.3)
#Coop.
1.9(0.2)
2.2(0.1)
2.0(0.3)
1.3(0.2)
#Hunt
0.6(0.)
0.4(0.0)
0.7(0.0)
0.6(0.1)
Table 2: Results in the standard setting of Agar.oo PBT: population training of parallel
(a) Cooperate
(b) Attack
Figure 9: Emergent strategies in standard Agar.oo:
PG policies: RR: best policy in the RR phase (w= 1. 1[); RPG: fine-tuned policy; RND: PG with RND bonus in the original game.
(a) agents cooperate to hunt efficiently; (b) a larger agent breaks the cooperation by atlacking the other.
well as popular exploration methods, i.c., count- count-based exploration (PG+CNT) Tang et al. 2017) and MAVEN (Mahajan et al. 2019). We also consider an additional baseline, DIAYN (Eysenbach et al., 2019), which discovers diverse skills using a trajectory-based diversity reward. For a fair comparison, use DIAYN to first pretrain diverse policies (conceptually similar to the RR phase), then evaluate the rewards for every pair of obtained policies to select the best policy pair (i.e., evaluation phase, shown with the dashed line in Fig. 6) and finally fine-tune the selected policies until convergence (i.e., fine-tuning phase). The results RPG and the 6 baselines are summarized in Fig. where RPG consistently discovers a strategy with a significantly higher payoff. Note that the strategy with the optimal payoff may not always directly emerge the RR phase, and there neither particular value of w constantly being the best candidate: e.g., in the RR phase,
[5. 0, 2| frequently produces a sub-optimal cooperative strategy (Fig. 7(a) with reward lower than other w values, but it can also occasionally lead to the optimal strategy (Fig. (b)). Whereas, with the fine-tuning phase, the overall procedure of RPG always produces the optimal solution. We visualize both two emergent cooperative strategies in Fig. 7 in the sub-optimal one (Fig. ((a)). two agents simply move to grid (1,1) together, stay still and wait for the monster, while in the optimal one (Fig. 7(b). agents meet each other first and then actively move towards the monster jointly, which further improves hunting efficiency.
Escalation: We can represent o(s, a1, i2; 2-dimensional vector containing (1) whether two agents are both in the lit grid and (2) the total consecutive cooperation steps. The original game corresponds to w = [1, 0.9.. We set Cmax = and show the total number of cooperation steps per episode for several selected w values throughout training in Fig. 8 where RR able to discover different NE strategies. Note that w I. 0] has already produced the strategy with the optimal payoff in this game, so the fine-tuning phase no longer needed.
Cosp taee
L.)
W-[L-) [11
w-:0 31
Originl
tstucdo
Figure 8: RR in Escalation
5.2 2- 2-PLAYER GAMES IN Agario
There are two different settings of Agario: (1) the standard setting, i.e., an agent gets a penalty of -v for losing mass 2, and (2) the more challenging aggressive setting, i.e., no penalty for mass loss. Note in both settings: (1) when an agent eats a mass x, it always gets a bonus of æ;; (2) if an agent loses all the mass, it immediately dies while the other agent still play in the game. The aggressive setting promotes agent interactions and typically leads to more diverse strategies in practice. Since both settings strictly define the penalty function for mass loss, we do not randomize this reward term. Instead, we consider two other factors: (I) the bonus for cating the other agent; (2) the prosocial level of both agents. We use 2-dimensional vector w [wo, Wi where ( S Wo, 241 S 1, to denote particular reward function such that (1) when eating a cell of mass x from the other agent, the bonus is Wo X x, and (2) the final reward is linear interpolation between 2(;;)) and 0.5 R(: 0) + R(: w.r.t. W1, i.e., when w/ 0, each agent optimizes its individual reward while when w1
two
agents have a shared reward. The original game in both Agar.io settings corresponds to w [1. OJ.
Standard setting: PG in the original game (w = 01, leads a typical trust-dilemma dynamics: the two agents first learn to hunt and occasionally Cooperate (Fig. (aa). i.e., eat script cell with the other agent close by; then accidentally Attacktttacks
Attacks the other agent (Fig. (b)). which yields a big
7

---

Published as a conference paper at ICLR 2021
PBT
w=|0.5,
w=[o, 1]
w=
RPG
RND
Rew.
3.3(0.2)
4. 4.8(0.6)
(.1
6.0k0.5)
8.9(0.3)
3.2(0.2)
#Attack
0,4(0.0)
0.7(0.2)
0.3
0,5(0.1)
0.9(0.1)
0,4(0.0)
#Coop.
0.0g..)
0.6(0.6)
2.3(0.3)
1.6(0.))
2.0(0:2)
0.0g..)
#Hlunt
0.7(0.1)
0.6(0.3)
0.3(0.0)
0.7(0.0)
0.9(0.1)
0.7(0.0)
Table 3: Results in the aggressive setting of Agario: PBT: population training of parallel PG policies; RR: w=10, 0J is the best candidate via RR; RPG: fine-tuned policy; RND: PG with RND bonus.
Figure 10: Sacrifice strategy,
w=[l, 11, aggressive setting.
Stas
Spla
Fat
Bart
Sartifie
Ganallr strr
Itu Tart Ser Coll
(exaler del
Hust upde
Figure 11: Perpetual strategy, w=[0.5, 1] (by chance), aggressive setting, i.e., two agents mutually sacrifice themselves. One agent first splits to sacrifice part of its mass to the larger agent while the other agent also does the same thing later to repeat the sacrifice cycle.
immediate bonus and makes the policy aggressive; finally policies converge to the non-cooperative equilibrium where both agents keep apart and hunt alone. The quantitative results are shown in training (PBT) and state-the-art exploration method for high- state, Random Network Distillation (RND) (Burda et al.] 2019). RND and PBT occasionally learns cooperative strategies while RR stably discovers cooperative equilibrium with = [1, 1), and the full RPG further improves the rewards. Interestingly, the best strategy obtained in the RR phase even has a higher Cooperate frequency than the full RPG: fine-tuning transforms the strong cooperative strategy to a more efficient strategy, which has a better balance between Cooperate and selfish Hunt and produces a higher average reward.
Tab. 2 Baselines include population-base
Similarly, we apply RPG in the aggressive setting and show results in Tab. 3 Neither PBT nor RND was able to find any cooperative strategies in the aggressive game while RPG stably discovers cooperative equilibrium with a significantly higher reward. We also observe diverse set of complex strategies in addition to normal Cooperate and Attack. Fig. 10 visualizes the Sacrifice strategy derived with w [1, 1]: the smaller agent rarely hunts script cells; instead, it waits in the corner for being eaten by the larger agent to contribute all its mass to its partner. Fig. IT shows another surprisingly novel emergent strategy by w [0.5, 1]: each agent first hunts individually to gain enough mass; then one agent splits into smaller cells while the other agent carefully eats portion of the split agent; later on, when the agent who previously lost mass gains sufficient mass, the larger agent similarly splits itself to contribute to the other one, which completes the (ideally) never-ending loop of partial sacrifice. We name this strategy Perpetual for its conceptual similarity to the perpetual motion machine. Lastly, the best strategy is produced by w [o, 0] with a balance between Cooperate and Perpetual: they cooperate to hunt script cells to gain mass efficiently and quickly perform mutual sacrifice as long as their mass sufficiently large for split-and-eat, Hence, although the RPG policy has relatively lower Cooperate frequency than the policy by w [0, 1], it yields significantly higher reward thanks to a much higher Attack (i.e., Sacrifice) frequency.
Aggressive setting:
5.3 LEARNING ADAPTIVE POLICIES
Monster-Hunt: We select policies trained
Oppo.
M.
M-Coop.
M-Alone.
Apple.
#C-H
16.3(19.2)
20.9(08)
14.2(18.0)
2.7(1.0)
by 8 different w values in the RR phase and use half of them for training the adaptive policy and the remaining half as hidden opponents for evaluation. We also make sure that both training and evaluation poli- cies cover the following 4 strategy modes: (1) M(onster): the agent always moves to- wards the monster; (2) M(onster)-Aoone: the agent moves towards the monster but
#S-H
1.2(0.4)
0.4(0.D
2.2(1.2)
2.2(14)
#Apple
12.4(7.3)
3.3(0.8)
10.9(7.0)
13.6(3.8)
Table 4: Stats. of the adaptive agent in Monster-Huu with hold-out test-time opponents. #C(cop.)- both agents catch the monster; #S(ingle)- the adaptive agent meets the monster alone; #Apple: ap- ple eating. The adaptive policy successfully exploits different opponents and rarely meets the monster alone. also tries to keeps apart from the other agent; (3) M(onster)-Coop: the agent seeks to hunt the monster together with the other agent; (4) Apple: the agent only eats apple. The evaluation results are shown in Tab. where the adaptive policy successfully exploits all the test-time opponents, including M(onster)-Alone, which was trained to actively avoids the other agent.
8

---

Published as a conference paper at ICLR 2021
Agent
Adapt.
Coop.
Comp.
Agar.io: We show the trained agent can choose to cooperate
or compete adaptively in the standard setting. We pick 2 co-
Opponent: Cooperative + Competitive
operative policies (i.e.. Cooperale preferred, w= [1, 0l) and
#Attack 0.2(0.0)
0.3(0.0)
(.1
2 competitive policies (i.e., Attuck preferred, w= 1 1 and
Rew.
0.7(0.7)
-0.2(0.6)
0. 0.8(0.5)
use half of them for training and the other half for testing. For hard challenge at test time, we switch the opponent within an episode, i.e., we use cooperative opponent in the first half and then immediately switch a competitive one, and vice versa. So, a desired policy should adapt quickly at halftime. Tab. compares the second-hale behavior of the adaptive agent with the oracle purt-competitive/coopraaai agents. The rewards of the adaptive agent is close to the oracle: even with half-way switches, the trained policy is able to exploit the cooperative opponent while avoid being exploited by the competitive one.
Opponent: Competitive -> Cooperative
#Coop.
1.0(0.3)
1. 1.4(0.4)
0.3(0.4)
Rew. 2.5(0.7)
3.6(1.2)
(.I(0.7)
Table 5: Adaptation test in Aganio. Op-
ponent type is switched half-way per episode. #Attack, #Coop.: episode statistics; Rew: agent reward. Adaptive agents' rewards are close to oracles.
RELATED WORK AND DISCUSSIONS
Our core idea is reward perturbation. In game theory, this is aligned with the quantal response equilibrium (McKelvey & Palfrey, 1995). a smoothed version of NE obtained when payoffs are perturbed by a Gumbel noise. In RL., reward shaping is popular for learning desired behavior in various domains (Ng et al.] 1999 Babes et al. 2008 Devlin & Kudenko D0, which inspires our idea for finding diverse strategic behavior. By contrast, state-space exploration methods (Pathak et al., 2017, Burda et al. 2019 Eysenbach et al.] 2019, (Shamma et al. 2020) only learn low-level primitives without strategy- level diversity (Baker et 20200).
RR trains a set of policies, which is aligned with the population-based training in MARL (Jaderberg
et al. 2017 2019 Vinyals et al. 2019 Long et al. 2020, Fooeetier et al. 2017). RR is conceptually
related to domain randomization (Tobin et al. (017)) with the difference that we train separate policies
instead of a single universal one, which suffers from mode collapse (see appendix D.2.3). RPG is also inspired by the map-elite algorithm (Cully et al. 2015) from evolutionary learning community, which optimizes multiple objectives simultancously for sufficiently diverse polices. Our work is also related to Forestier et al. (2017), which learns a set of policies w.r.t. different fitness functions in the single- agent setting. However, they only consider a restricted fitness function class, i.c., the distance to each object in the environment, which can be viewed as special case of our setting. Besides, RPG helps train adaptive policies against a set of opponents, which is related to Bayesian games (Dekel et al. Harrline et al. 2015). In RL, there are works learning when to cooperate/compete (Litiman Peysakhovich & Lerer 2018a] Kleiman- Weiner et al.] 2016) Woodward et al. 2019 McKee
2004
2001
et al.
2020), which is special case of ours, learning robust policies (Li et al. 2019 Shen & How
2019
Hu et al. 2020). which complements our method.
Although we choose decentralized PG in this paper, RR can be combined with any other multi-agent learning algorithms for games, such as fictitious play (Robinson) 1951 Monderer Shapley 1996.
Heinrich & Silver 2016 Kamra et al. 2019 |Han & Hu (2019), double-oracle (McMahan et al. 2003
Lanctot et al. [017 7| Wang et al.] 2019 Balduzzi et al. 2019) and regularized self-play (Foerster et al.
| Perolat et al.) 2020 Bai & Jin 2020). Many of these works have theoretical guarantees to
find an (approximate) NE but there is little work focusing on which NE strategy these algorithms can converge to when multiple NEs exist, e.g., the stag-hunt game and its variants, for which many learning dynamics fail to converge to a prevalence of the pure strategy Stag (Kandori et al. 1993
Ellison 1993
Fang et al. 2002; Skyrms & Pemantle 2009 Golman & Page 2010)..
In this paper, we primarily focus how reward randomization empirically helps MARL discover better strategies in practice and therefore only consider stag hunt as a particularly challenging example where "optimal" NE with high payoff for every agent exists. In general cases, can select a desired strategy w.r.t. an evaluation function. This is related to the problem of equilibrium refinement (or equilibrium selection) (Selten 1965 1975| Myerson] 1978). which aims to find a subset of equilibria satisfying desirable properties, e.g., admissibility (Banks & Sobell 1987). subgame perfection (Selten) 1965). Pareto efficiency (Bernheim et al. 1987) or robustness against opponent's 's deviation from best response security-relater applications (Fang et al. 2013 An et al. 2011).

---

Published as a conference paper at ICLR 2021
ACKNOWLEDGMENTS
This work is supported by National Key R&D Program of China (2018YFB0105000) Co-author Fang supported, in part, by a research grant from Lockheed Martin. Co-author Wang is supported, in part, by gifts from Qualcomm and TuSimple. The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of the funding agencies. The authors would like thank Zhuo Jiang and Jiayu Chen for their support and input during this project. Finally, we particularly thank Bowen Baker for initial discussions and suggesting the Stag Hunt game our research testbed, which eventually leads to this paper.
REFERENCES
Bo An. Milind Tambe, Fernando Ordonez, Eric Shich, and Christopher Kiekintveld. Refinement of strong stackelberg equilibria in security games. In Twenty-Fifth AAAI Conference on Artificial Intelligence, 2011.
Monica Babes, Enrique Munoz de Cote, and Michael Littman. Social reward shaping in the prisoner's ' dilemma. In Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems-Volume 3, pp. 1389-1392. International Foundation for Autonomous Agents and Multiagent Systems, 2008.
join
Yu Bai and Chi Jin. Provable self-play algorithms for competitive reinforcement learning, arXiv preprint 2xXv:22002.0401, 2020.
Bowen Baker, Ingmar Kanitscheider, Todor Markov, Yi Wu, Glenn Powell, Bob McGrew, and Igor Mordatch. Emergent tool use from multi-agent autocurricula, 2019.
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 on Learning Representations, 2020.
David Balduzzi, Marta Garnelo, Yoram Bachrach, Wojciech M Czamecki, Julien Perolat, Max Jaderberg, and Thore Graepel. Open-ended learning symmetric zero-sum games. arXiv preprint 1rX1vv/901.000 11.9000080066 106, 2019.
Jeffrey S Banks and Joel Sobel. Equilibrium selection in signaling games. Econometrica: Journal of the Econometric Society, pp. 647-661, 1987.
Douglas Bernheim, Bezalel Peleg, and Michael D Whinston. Coalition-proof Nash equilibria i. concepts. Journal of Economic Theory, 42(1):1-12, 1987.
George W Brown. Iterative solution of games by fictitious play. Activity analysis of production and allocation, 13(1):374-376, 1951.
Yuri Burda, Harrison Edwards, Amos Storkey, and Oleg Klimov. Exploration by random network distillation. In International Conference on Learning Representations, 2019.
Murray Campbell, A Joseph Hoane Jr, and Feng-hsiung Hsu. Deep blue. Artificial intelligence, 134 (1-2):57-83, 2002.
Antoine Cully, Jeff Clune, Danesh Tarapore, and Jean-Baptiste Mouret. Robots that adapt like animals. Nature, 521(7553):503-507, 2015.
Eddie Dekel, Drew Fudenberg, and David K Levine. Learning to play Bayesian games. Games and Economic Behavior, 46(2):282-303, 2004.
Sam Devlin and Daniel Kudenko. Theoretical considerations of potential- reward shaping for multi-agent systems. In The 10th International Conference on Autonomous Agents and Multiagent Systems- Volume I, pp. 225-232 International Foundation for Autonomous Agents and Multiagent Systems, 2011.
Glenn Ellison.
Learning, local interaction, and coordination. Econometrica: Journal of the Econo- metric Society, pp. 1047-1071, 1993.
10

---

Published as a conference paper at ICLR 2021
Benjamin Eysenbach, Abhishek Gupta, Julian Ibarz, and Sergey Levine. Diversity is all you need: Learning skills without a reward function. International Conference on Learning Representations, 2019.
Christina Fang, Steven Orla Kimbrough, Stefano Pace, Annapurna Valluri, and Zhiqiang Zheng. On adaptive emergence trust behavior in the game of stag hunt. Group Decision and Negotiation, 11(6):449 467, 2002.
Fei Fang. Albert Xin Jiang, and Milind Tambe. Protecting moving targets with multiple mobile resources. Journal of Artificial Intelligence Research, 48:583-634, 2013.
Jakob Foerster, Richard Y Chen, Maruan Al-Shedivat, Shimon Whiteson, Pieter Abbeel, and Igor Mordatch. Learning with opponent-leamingg awareness. In Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems, pp. 122-130. International Foundation for Autonomous Agents and Multiagent Systems, 2018
Sébastien Forestier, Rémy Portelas, Yoan Mollard, and Pierre Yves Oudeyer. Intrinsically motivated goal exploration processes with automatic curriculum learning. arXiv preprint arXiv: 1708.02 2017.
Rong Ge, Furong Huang. Chi Jin, and Yang Yuan. Escaping from saddle points online stochastic gradient for tensor decomposition. Conference on Learning Theory. pp. 797-842, 2015.
Russell Golman and Scott Page. Individual and cultural learning in stag hunt games with multiple actions. Journal of Economic Behavior & Organization, 73(3):359-376, 2010.
Dylan Hadfield-Menell, Smitha Milli, Pieter Abbeel, Stuart Russell, and Anca Dragan. Inverse reward design. In Advances in neural information processing systems, pp. 6765-6774, 2017.
Jiequn Han and Ruimeng Hu. Deep fictitious play for finding Markovian Nash equilibrium in multi-agent games. arXiv preprint 1912.01 809,, 2019.
Jason Hartline, Vasilis Syrgkanis, and Eva Tardos. No-regret learning in Bayesian games. In Advances in Neural Information Processing Systems, pp. 3061-306100 2015.
Johannes Heinrich and David Silver. Deep reinforcement learning from self-play in imperfect- information games. arXiv preprint 12Xiv:1603..0122,,000 2016.
Hengyuan Hu, Adam Lerer, Alex Peysakhovich, and Jakob Foerster. Other-play for zero-shot coordination. arXiv preprint arXiv:2003.02973 2020.
Max Jaderberg, Valentin Dalibard, Simon Osindero, Wojciech Czarnecki, Jeff Donahue, Ali Razavi, Oriol Vinyals, Tim Green, lain Dunning, Karen Simonyan, et al. Population based training of neural networks. arXiv preprint arXiv: /tt::/111.0990 2017.
Max Jaderberg, Wojciech M Czarnecki, lain Dunning, Luke Marris, Guy Lever, Antonio Garcia Castaneda, Charles Beattie, Neil C Rabinowitz, Ari S Morcos, Avraham Ruderman, al. Human- level performance in 3D multiplayer games with population based reinforcement learning. Science, 364(6443):859 8555 2019.
Nitin Kamra, Umang Gupta, Kai Wang, Fei Fang, Yan Liu, and Milind Tambe. Deep fictitious play for games with continuous action spaces. In Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems, pp. 2042-2044. International Foundation for Autonomous Agents and Multiagent Systems, 2019.
Michihiro Kandori, George J Mailath, and Rafael Rob. Learning, mutation, and long run equilibria in games. Econometrica: Journal of the Econometric Society, pp. 29-56, 1993.
Max Kleiman- Aleiman-Weiner, Mark Ho, Joseph L Austerweil, Michael L Littman, and Joshua B Tenen- baum. Coordinate to cooperate compete: abstract goals and joint intentions in social interaction. In CogSci, 2016.
Robert Kleinberg, Yuanzhi Li, and Yang Yuan. An alternative view: When does sgd escape local minima? arXiv preprint urX2v 2018.

---

Published as a conference paper at ICLR 2021
Mare Lanctot, Vinicius Zambaldi, Audrumas Gruslys. Angeliki Lazaridou, Karl Tuyls, Julien Pérolat, David Silver, and Thore Graepel. unified game-theoretic approach to multiagent reinforcement learning. In Advances in Neural Information Processing Systems, pp. 4190-4203, 2017.
Joel Z Leibo, Vinicius Zambaldi, Mare Lanctot, Janusz Marecki, and Thore Graepel. Multi-agent reinforcement learning in sequential social dilemmaas. In Proceedings of the 16th Conference Autonomous Agents and MultiAgent Systems, pp. 464-473, 2017.
Sergey Levine, Chelsea Finn, Trevor Darrell, and Pieter Abbeel. End-to-end training of deep visuomotor policies. The Journal of Machine Learning Research, 17(1):1334-1373 2016.
Richard Li, Allan Jabri, Trevor Darrell, and Pulkit Agrawal. Towards practical multi-object manipula- tion using relational reinforcement learning. In Proceedings of the IEEE International Conference Robotics and Automation (ICRA), 2020.
Shihui Li, Yi Wu, Xinyue Cui, Honghua Dong, Fei Fang. and Stuart Russell. Robust multi-agent reinforcement learning via minimax deep deterministic policy gradient. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 4213-4220, 2019.
Michael Littman. Friend-or-foe q-learning general-sum games. In JCML, volume pp. 322-328. 2001.
Qian Long, Zihan Zhou, Abhinav Gupta, Fei Fang, Wu, and Xiaolong Wang. Evolutionary population curriculum for scaling multi-agent reinforcement learning. In International Conference on Learning Representations, 2020.
Ryan Lowe, Yi Wu, Aviv Tamar, Jean Harb, OpenAl Pieter Abbcel, and Igor Mordatch. Multi-agent actor-critic for mixed cooperative-competiiv environments. In Advances in neural information processing systems, pp.
2017.
Anuj Mahajan, Tabish Rashid, Mikayel Samvelyan, and Shimon Whiteson. Maven: Multi-agent variational exploration. In Advances in Neural Information Processing Systems, pp. 761 7611-7622, 2019.
Kevin R McKee, Ian Gemp, Brian McWilliams, Edgar A DuéñezzGuzmán Edward Hughes, and Joel Z Leibo. Social diversity and social preferences mixed-motive reinforcement learning. arXiv preprint arXiv:2002.023225 2020.
Richard D McKelvey and Thomas Palfrey. Quantal response equilibria for normal form games. Games and economic behavior, 10(1):6-38. 1995.
H Brendan McMahan, Geoffrey J Gordon, and Avrim Blum. Planning in the presence of cost functions controlled by an adversary. In Proceedings of the 20th International Conference on Machine Learning (ICML-03), pp. 536-543, 2003.
Piotr Mirowski, Razvan Pascanu, Fabio Viola, Hubert Soyer, Andrew Ballard, Andrea Banino, Misha Denil, Ross Goroshin, Laurent Sifre, Koray Kavukcuoglu, et al. Learning to navigate in complex environments. arXiv preprint 161iv:1611.03677. 2016.
Dov Monderer and Lloyd S Shapley. Potential games. Games and economic behavior, 14(1):124-14 1996.
Roger B Myerson. Refinements of the Nash equilibrium concept. International journal of game theory, 722)733800 1978.
John Nash. Non-cooperative games. Annals of mathematics, pp. 286-295, 1951.
Andrew Y Ng, Daishi Harada, and Stuart Russell. Policy invariance under reward transformations: Theory and application reward shaping. In ICML, volume 99, pp. 278-287, 1999.
Andrew Y Ng. Stuart J Russell, et al. Algorithms for inverse reinforcement learning. In Ieml, volume 1, pp. 2, 2000.
12

---

Published as a conference paper at ICLR 2021
OpenAI, :, Christopher Berner, Greg Brockman, Brooke Chan, Vicki Cheung, Przemystaw Debiak, Christy Dennison, David Farhi, Quirin Fischer, Shariq Hashme, Chris Hesse, Rafal Józefowicz, Scott Gray, Catherine Olsson, Jakub Pachocki, Michael Petrov, Henrique Pondé de Oliveira Pinto, Jonathan Raiman, Tim Salimans, Jeremy Schlatter, Jonas Schneider, Szymon Sidor, llya Sutskever, Jie Tang, Filip Wolski, and Susan Zhang. Dota 2 with large scale deep reinforcement learning, 2019.
Deepak Pathak, Pulkit Agrawal, Alexei A Efros, and Trevor Darrell. Curiosity-driver exploration by self-supervised prediction. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition Workshops, pp. 16-17, 2017.
Julien Perolat, Remi Munos, -aan-BBptisteeee Lespiau, Shayegan Omidshafiei, Mark Rowland, Pedro Ortega, Neil Burch, Thomas Anthony, David Balduzzi, Bart De Vylder, al. From Poincare recurrence to convergence in imperfect information games: Finding equilibrium via regularization. arXiv preprini 20Vi::2002.08566. 2020.
Alexander Peysakhovich and Adam Lerer. Consequentialist conditional cooperation in social dilem- mas with imperfect information. In International Conference on Learning Representations, 201 8a.
Alexander Peysakhovich and Adam Lerer. Prosocial learning agents solve generalized stag hunts better than selfish ones. In Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems, pp. 2043-2044, International Foundation for Autonomous Agents and Multiagent Systems, 2018b.
Julia Robinson. An iterative method solving game. Annals of mathematics, pp. 296-301, 1951.
Jean-Jacques Rousseau. A discourse on inequality. Penguin, 1984.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.00347, 2017.
R Selten. Reexamination of the perfectness concept for equilibrium points in extensive games. International Journal of Game Theory, 4(1):25-55, 1975.
Reinhard Selten. Spieltheoretische behandlung eines oligopolmodells mit nachfrageträgheit: Teil i: Bestimmung des dynamischen preisgleichgewichs. Zeitschrift für die gesamte Staatswis- senschaft/Journal of Institutional and Theoretical Economics, (H. 2):3013324, 1965.
Claude E Shannon. Xxii. programming a computer for playing chess. The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science, 21(314))256-27,, 1950.
Archit Sharma, Shixiang Gu, Sergey Levine, Vikash Kumar, and Karol Hausman. Dynamics-aware unsupervised discovery of skills. In International Conference on Learning Representations, 2020.
Macheng Shen and Jonathan P How. Robust opponent modeling via adversarial ensemble reinforce- ment learning in asymmetric inperffectiifformttion games. arXiv preprint arXiv:1909 08735, 2019.
David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. Mastering the game of go without human knowledge. Nature, 550(7676):354-355 2017.
David Silver, Thomas Hubert, Julian Schritwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Mare Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, et al. A general reinforcement learning algorithm that masters chess, shogi, and go through self-play, Science, 362(6419): 1140-1144, 2018
Satinder P Singh, Michael J Kearns, and Yishay Mansour. Nash convergence of gradient dynamics in general-sum games. In UAI, pp. 541-548, 2000.
Brian Skyrms. The stag hunt and the evolution of social structure. Cambridge University Press, 2004.
Brian Skyrms and Robin Pemantle. A dynamic model of social network formation. In Adaptive networks, pp. 231-251. Springer, 2009.
13

---

Published as a conference paper at ICLR 2021
Haoran Tang, Rein Houthooft, Davis Foote, Adam Stooke, OpenAI Xi Chen, Yan Duan, John Schulman, Filip DeTurek, and Pieter Abbeel. #exploration: study of count-based exploration for deep reinforcement learning. In I. Guyon, U. V. Luxburg, S. Bengio. H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Advances Neural Information Processing Systems 30, pp. 2753-2766 2017.
Josh Tobin, Rachel Fong, Alex Ray, Jonas Schneider, Wojciech Zaremba, and Pieter Abbeel. Domain randomization for transferring deep neural networks from simulation to the real world. 2017 IEEE/RSJ international conference intelligent robots and systems (IROS), pp. 23-30. IEEE, 2017.
Oriol Vinyals, Timo Ewalds, Sergey Bartunov, Petko Georgiev, Alexander Sasha Vezhnevets, Michelle Yeo, Alireza Makhzani, Heinrich Küttler, John Agapiou, Julian Schrittwieser, et al. Starcraft II: A new challenge for reinforcement learning. arXiv preprint arXiv:/708.04755 2017.
Oriol Vinyals, Igor Babuschkin, Wojeiech M Czamecki, 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)3350-33) 2019.
Yufei Wang, Zheyuan Ryan Shi, Lantao Yu, Wu, Rohit Singh, Lucas Joppa, and Fei Fang. Deep reinforcement learning for green security games with real-time information. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 1401-1408, 2019.
Wikipedia. Agar.oo, 2020.
URL http: //ep www.peiiii......mmmmmm. wtg.wii.....//kk.k..... wwwp:/iiki/aaaa.../..... io [http://en.wikieeddine httppedda..rgwwikkiiiii Agar.oo; accessed 20200.
Mark Woodward, Chelsea Finn, and Karol Hausman. Learning to interactively learn and assist. arXiv preprint ar arXiv: 10187, 2019.
Yi Wu, Yuxin Wu, Georgia Gkioxari, and Yuandong Tian. Building generalizable agents with realistic and rich 3D environment. arXiv preprint arXiv: /rXIv=/801.02209, 2018
Yuxin Wu and Yuandong Tian. Training agent for first-person shooter game with actor-critic curriculum learning. 2016.
Tianhe Yu, Deirdre Quillen, Zhanpeng He, Ryan Julian, Karol Hausman, Chelsea Finn, and Sergey Levine. Meta-world: A benchmark and evaluation for multi-task and meta reinforcement learning. In Conference on Robot Learning (CoRL). 2019.
Brian Ziebart, Andrew Maas, Andrew Bagnell, and Anind Dey. Maximum entropy inverse reinforcement learning. In Aaai, volume 8, pp.
Chicago, II. USA, 2008.
14

---

Published as a conference paper at ICLR 2021
We would suggest to visit wat.:ttee./.ttee..oooo..../////s for example videos.
A PROOFS
Proof of Theorem I. We apply self-play policy gradient to optimize 81 and 0g. Here we consider a projected version, i.e., if at some time 81 02 [0, 1], project it to [0, to ensure it is valid distribution.
We first compute the utility given pair (01, 02)
U1, 02) =a0 02 + o01 (1 - 02) + ((1 - - d(1 [1]0 01)(1 02)
U2(01, B2) =a0,02 22 + 601 (1 02) + c(1 - + -(ddd((1)))))))))) 01)(1 02).
We can compute the policy gradient
VU1 02) =a0- + c(1 - 02) - 602 d(1 - 02) = (a b-c)0 + c- d
UU2(01, 02) =a02 60, c(1 01) d(1 01) (a b- c)0 +
Recall in order to find the optimal solution both 8, and 0₂ need to increase. Also note that the initial 81 and 0g determines the final solution. In particular, only if 01 and 0g are increasing at the beginning. they will converge to the desired solution.
To make either 01 or Og increase, we need to have
(a + d c)0 + c -
(a d c)02 +
Consider the scenario a - eld - c). In order to make Inequality equation to hold, we need at 1 If we initialize 0, ~ [0. 1] and 02 ~ [0, 1]. the probability of either 0,, 0g 2 1 is 1
least either 0,, 02 2 Itc
Itc
Itc
=
2c 142c+e2 (c).
Using a similar observation as in Theorem ! we know necessary condition to make PG converge sub-optimal NE
Proof of Theorem
(a + b c)01 + c (c-d<t d< (a + d b-loddd-b+++-e -c- d<
Based generating scheme a, b, c, and the initialization scheme 0, 02 verify that Therefore, via a union bound, we know
P ((a - b c)01 + 0 (a + d b- c)0₂ d < 0) I 0.6.
Since each round is independent, the probability that PG fails for all times is upper bounded by N. Therefore, the success probability is lower bounded by 1- 0.6 11 exp (-Ω2 (N)).
B ENVIRONMENT DETAILS
B. Iterative Stag-Huse Hunt
In Iterative Hunt, two agents play rounds, that is, both PPO's trajectory length and episode length are 10. Action of each agent is 1-dimensional vector, denotes taking Stag action and t, = denotes taking Hare action. Observation of each agent is actions taking by itself and its opponent in the last round, i.e., of {a [a {0, 1]), where
[t,, E (0, 1}}, where f; = 0
r denotes the playing round. Note that neither agent has taken action at the first round, so the observation o; -11.-
15

---

Published as a conference paper at ICLR 2021
450
400
350
RR
Warm-start
Fine-tuning
300
Rewards
250
200
150
300
PG
PBT
RPG
0.0
0.5
1.0
1.5
2.0
2.5
3.0
35
4.0
Episodes
165
Figure 12: Results Monster-Hunt with 3 agents (3 seeds).
B.2 Monster-Hunt
In Monster-Hunf, agents move one step in any of the four cardinal directions (Up, Down, Left, Right) at each timestep. Let a; = {4,, i E {0, 1}} denote action of agent i, where f, is a discrete 4-dimensional one-hot vector. The position of each agent can not exceed the border of 5-by-5 grid, where action execution is invalid. One Monster and two apples respawn in the different grids at the initialization. If agent eats (move over in the grid world) an apple, it can gain 2 points. Sometimes, two agents may try to eat the same apple, the points will be randomly assigned to only one agent. Catching the monster alone causes an agent lose 2 points, but if two agents catch the stag simultaneouslyy each agent can gain points. At each time step, the monster and apples will respawn randomly elsewhere in the grid world if they are wiped. In addition, the monster chases the agent closest each timestep. The monster may move over the apple during the chase, this case, the agent will gain the sum of points if it catches the monster and the apple exactly. Each agent's observation o; a 10-dimensional vector and formed by concatenating its own position pi, the other agent's 's position Pi-í, monster's 's positionpmonster and sorted apples' position Papple0. Pupplel, i.c., of (Ps: P1- Pmonster: Papple0 P i E {0, 1)}, where p (u, v) denotes the 2-dimensional coordinates in the gridworld.
B.3 Monster-Hunt WITH MORE THAN 2 AGENTS
Here consider extending RPG to the general setting of N agents. In most of the multi-agent games, the reward function are fully symmetric for the same type of agents. Hence, as long as we can formulate the reward function in linear form over a feature vector and shared weight, i.e. iN; Φ(8 .I.......... aN; w, we can directly apply RPG without any modification by setting R {Rw (s, aj..... aN; i) Φ(s, 01..... ON; i w). Note that typically the dimension of the feature vector <(-) remains fixed w.r.t. different number of agents (N), For example,
in the Agan.o game, matter how many players there in the game, the rule of how to get reward bonus and penalties remains the same.
Here, experiment RPG in Monster-Hunt with 3 agents. The results shown in Fig. 12 We consider baselines including the standard PG (PG) and population-based training (PBT), RPG reliably discovers a strong cooperation strategy with substantially higher reward than the baselines.
B.4 Escalation
In Escalation, two agents appear randomly and one grid lights up at the initialization. If two agents step on the lit grid simultaneously, each agent can gain 1 point, and the lit grid will go out with an adjacent grid lighting up. Both agents can gain point again they step on the next lit grid together. But if one agent steps off the path, the other agent will lose 0.9L points, where L is the current length of stepping together, and the game is over. Another option is that two agents choose to step off the path simultaneously. neither agent will be punished, and the game continues. As the length I. of stepping together increases, the cost of betrayal increases linearly. a; (li, i (0, 1)} denotes
16

---

Published as a conference paper at ICLR 2021
action of agent i, where t2 is discrete 4- d-dimensional one-hot vector. The observation a, of agent i is composed of its own position pt, the other agent's positionp1-: and the lit grid's position Pia- lee. 0j = (Pi, Pla E {0, 1],, where p (u, v) denotes the 2-dimensional coordinates in the gridworld. Moreover, we utilize GRU to encode the length L. implicitly, instead of observing that explicitly.
B.5 Agario
In the original online game Aganio, multiple players are limited in a circle petri dish. Each player controls one or more balls using only a cursor and 2 keyboard keys "space" and "w". all balls belonging to the player will move forward to where the cursor pointing at. Balls larger than a threshold will split to 2 smaller balls and rush ahead when the player pressing the key "space". Balls larger than another threshold will emit tiny motionless food-like balls when the player pressing "w". Agar.io has many play modes like "Free-For-All" mode (All players fight for their own and can eat each other) and "Team" mode (Players are separated two groups. They should cooperate with other players in the same group and eat other players belonging to another group).
We simplified settings of the original game Agario: Now agents don't need to emit tiny mo- tionless balls and all fight with each other (FFA mode). The action space of the game is larget x (split, no_splil]. largel E [0, 1] means the target position that all balls belonging to the agent move to. binary action split or no_ no_split means whether the player chooses to split, which will cause all balls larger than a threshold split to 2 smaller ones and rush ahead for short while. These split balls will re-merge after some time, then the agent can split again. When one agent's 's ball meets another agent's 's ball and the former one is at least 1.2 times larger than the later, the later will be eaten and the former will get all its mass. The reward is defined as the increment of balls' mass. So every agent's 's goal is getting larger by cating others while avoid being eaten. But larger ball moves slower. So it's really hard to catch smaller balls only by chasing after it. Split will help, but it needs high accuracy to rush to the proper direction. In our experiments, there were 7 agents interacting with each other. 2 agents were learned by our algorithm and would quit the game if all balls were eaten. agents were controlled by a script and would reborn at a random place if all balls were eaten. bearn-based agents were initialized larger than script- saspt- agents so it basically one-way catching. In this setting, cooperation was the most efficient behavior for to gain positive reward, where they coordinated to surround script-based agents and caught them.
agents
Observation space: We denote partial observation of agent as O;, which includes global infor- mation of the agent (denoted as Oi.giobal) and descriptions of all balls around the agent (includ- ing balls owned by the agent, denoted as Oj,balls- and Os,balls = [Oi,balt, Os,ball,2 ..., Og Dal } where Oi,ball,j denotes the j-th ball around the agent and there are m observed balls in all). Oiggiobal = (4,,bbe obs Di, centers Ui ai,aeves own, T2 scriptt Ritother: Os,last Ti Timaaz: Timmens m where li,obs, ois (they are both ID filled with a real number, from here the form like (ID, real) will be used as the abbreviation) are the length and width of the agent's observation scope, Pi, (2D, real) is its center position, U; (2D, real) is the speed of its center, Si,alive (ID, binary) is whether the other learn-based agent is killed, Ni,oww, Reiscript Nii (1D, real) are numbers of each type of balls nearby (3 types: belonging to me, or belonging to a script agent, or belonging to another learn-based agent), at,tast(DD, real) is the agent's 's last action, Ti,maz: Ti Fimm real) are maxi- mal and minimal radius of all balls belonging to the agent. for any j = 1, 2, m, bullll.. = (Pejiretative Pt, Pt.j,abeolute: Vi.j, rurhh Ft.j. log(rr.)) di,j Ci.j.maz: Ci.j.min $t.. t.,... }. where Peelttetttve: abbj.abe (2D, real) are the ball's relative and absolute position, Vayy is its speed, ball splits to 2 smaller balls, these 2 balls will
U.jirush is the ball's additional rushing speed(when get additional speed and it's called jussh otherwise U.j.ush = 0), rs.s rID, real) is its radius, d is the distance between the ball and the center of the agent, Ci.imaz: mi.j (ID, binary) are whether the ball can be eaten by the maximal or minimal balls of the observing agent, rem (1D, binary) is whether the ball is able to remerge at present. tt,,(DD, one hot) is the type of the ball.
The scrept-base agent can automatically chase after and split towards other smaller agents. When facing extreme danger (we define "extreme danger" as larger learn-based agents being very close to it), it will use 3-step deep-fist-search to plan best way for escape. More details of the script can be seen in our code. We played against the script-base agent using human intelligence for many times and we could never hunt when having only one ball and rarely catch it by split.
17

---

Published as a conference paper at ICLR 2021
C TRAINING DETAILS
C.I GRIDWORLD GAMES
In Monster-Huue Huntt and Escalation, agents' networks are organized by actor-critic (policy-value) architecture. We consider N = 2 agents with a policy profile = {To, T parameterized by (8o. }. The policy network म; takes observation o, as input, two hidden layers with 64 units are followed after that, and then outputs action ag. While the value network takes as imput observations {oo. 01 } and outputs the V-value of agent i, similarly two hidden layers with 64
of two agents, units are added before the output.
In Escalation, we also place additional GRU module before the output in policy network and value network respectively, to infer opponent's 's intentions from historical information. Note that 64-dimensional hidden state of GRU l will change if the policy network is updated. In order to both keep forward information and use backward information to compute generalized advantage estimate (GAE) with enough trajectories, we split buffer data into small chunks, e.g., 10 consecutive timesteps as a small data chunk. The initial hidden state hinit, which is the first hidden state ho. is kept for each data chunk, but do another forward pass to re-compute (hi, ..., hM-1), where M represents the length of one data chunk, and keep buffer-reuse low, e.g., 4 in practice.
Agents in Monster-Hune and Escalation are trained by PPO with independent parameters. Adam optimizer is used to update network parameters and each experiment is executed for 3 times with random seeds. More optimization also utilizes GRU modules to infer opponent's s identity during adaption training and the parallel threads are set to 64.
settings are in Tabló In addition, Monster-Humt
Count-based exploration: We just add the count-based exploration intrinsic reward Tint to the environment reward during training. when the agent's observation is o, T'mt = a/n, where a is a hyperparameter adjusted properly (0.3 in Monster-Hunt and I in Esculation) and ni, is the number of times the agent have the observation o.
DIAYN: In Monster-Hunt, we use DIAYN to train 10 diverse policy in the first 140k episodes (DIAYN's discriminator has 3 FC layers with 256, 128, 10 units respectively) and choose the policy which has the best performance in Monster-Huntt 's reward settings to fine-tune in the next 280k episodes. Note that DIAYN doesn't 't have warm-start phase before fine-tuning its original paper so we didn't 't do so as well. Note that in the first unsupervised learning phase, DIAYN does not optimize for any specific reward function. Hence, we did not plot the reward curve for DIAYN in Fig.7 for this phase. Instead, we simply put dashed line showing the reward of the best selected pair of policies from DIAYN pretraining.
MAVEN: We use the open-sourced implementation of MAVEN from
com/
Anu Maha MahaaaaCXE fanCxf /MAVEN
each PBT trial, we straightforward train the same amount of parallel PG policies as RPG with different random seeds in each problem respectively and choose the one with best performance as the final policy. Note that the final training curve is averaged over 3 PBT trials.
Population-based training:
C.2 Agario
In Agarioo we used PPO our algorithm and agents' networks were also organized by actor-critic (policy-value) architecture with a GRU unit (i.c., PPO-GRU), We consider N = 2 agents with a policy profile π = {To, Ti sharing parameter f. The policy network x; takes observation o, as input. At the beginning, like (Baker et al. 2019), Or,blll is separated to 3 groups according to balls' types: oiowbbllss oi,ccriptballs and oitheerballls- 3 different multi-head attention models with 4 heads and 64 units for transformation of keys, inquiries and values are used to embed information of types of balls respectively, taking corresponding part of 0,,balls as values and inquiries and Os.giobal as keys. Then their outputs are concatenated and transformed by an FC layer with 128 units before being sent to GRU block with 128 units. After that, the hidden state is copied to 2 heads for policy's 's and value's output. The policy head starts with FC layers both with 128 units and ends with 2 heads to generate discrete(split or no no_split) and continuous(targe)) actions. The value head has 3 FC layers with 128, 128, unit respectively and outputs real number.
18

---

Published as a conference paper at ICLR 2021
Hyper-parameters
Value
Initial learning rate
le-3
Minibatch size
320 chunks of 10 timesteps lc-5
Adam stepsize (e)
Discount rate (7)
0,99
GAE parameter (A)
0.95
Value loss coefficient
Entropy coefficient
0.01
Gradient clipping
0.5
PPO clipping parameter
0.2
Parallel threads
(55Sccalltton)2256MMMttteee
PPO epochs
4
reward scale parameter
episode length
50
Table 6: PPO hyper-paramettrs used in Gridworld games, learning rate is linearly annealed during training.
Value
Learning rate
2.5e-4
Minibatch size
* 512 chunks of 32 timesteps
Adam stepsize (c)
le-5
Discount rate (7)
0.995
GAE parameter (A)
0.95
Value loss coefficient
0.5
action loss coefficient Entropy coefficient
1
(d0scdis) 0.0025(continuoou)
Gradient clipping
20
PPO clipping parameter
0.1
Parallel threads
128
PPO epochs
4
episode length
128
Table 7: PPO hyper-parameters used in Agar.io
PPO-GRU was trained with 128 parallel environment threads. Agarcio's episode length was uniform- randomly sampled between 300 and 400 both when training and evaluating. Buffer data were split to small chunks with length = 32 in order to diversify training data and stabilize training process. and the buffer was reused for 4 times to increase data efficiency. Hidden states of each chunk except at the beginning were re-computed after each reuse to sustain PPO's "on-policy" property much as possible. Action was repeated for 5 times in the environment whenever the policy was executed and only the observation after the last action repeat was sent to the policy. Each training process started with curriculum-lcarning in the first 1.5e7 steps: Speed of script agents was multiplied with z, where x is uniformly mamoles between max (n le7) and min 1, max (n 5e6)/566) } at the beginning of each episode, where n was the steps of training. After the curriculum learning, Speed was fixed the standard. Each experiment was executed for times with different random seeds. Adam optimizer was used to update network parameters. More optimization hyper-panne parameeet settings are in Tab
D ADDITIONAL EXPERIMENT RESULTS
D.1 Monster-Huun
In Monster-Hunt, we set Cmax = 5 for sampling w. Fig. 13 illustrates the policies discovered by several selected w values, where different strategic modalities can be clearly observed: e.g., with w [0, 5, 0), agents always avoid monsters and only eat apples. In Fig. 14] it's worth noting that [5, 0, could yield the best policy profile (i.e., two agents move together to hunt the monster.)
19

---

Published as a conference paper at ICLR 2021
#Coop.-Hunt
#Single-Hun
#Apple
25
25
35-
25
Frequency
15
Frequency
15
Frequency
20
15
5-
Episodes
Episodes
Episodes
W 151151
W= [V144,
== [0,5.0]
w=15,0,51
Original
Figure 13: Statisties of different policy profiles in Monster- Hantterr-untt.eee -Crteerp--.....oo-------o frequency of both agents catching the monster; #Single-Hunt: frequency of agents meeting the monster alone; #Apple: apple frequency.
205.76
257.55
217.9
150
113.0912.11
75.63
74.03
100
57.3
Ofigial
Shaw Roward
[5.1.5)
122 23.23
(0.5.00
15.0.1
Finetrre
Figure 14: Results in original Monster-Hunt, Original: PG in the original game; Share reward: PG with shared reward the original game; Finetune: fine-tuning the best policy obtained in the RR phase and yielding the highest reward in the original game.
and doesn't 't even require further fine-tuning with some seeds. But the performance of w = [5, 0, 2] is significantly unstable and it may converge another NE (i.e.. two agents move a corner and wait for the monster.) with other seeds. So w = [5, 0, 5]. which yields stable strong cooperation strategies with different seeds, will be chosen in RR phase when the obtained rewards from different policies in Fig. [4 where the policies learned by RPG produces the highest rewards.
[5, 0, 2] performs poorly. We demonstrate
D.2 Agario
D.2.1 STANDARD SETTING
We sampled 4 different w and they varied in different degrees of cooperation. We also did experiments using only baseline PG or PG with intrinsic reward generated by Random Network distillation (RND) compare with RPG. RR lasted for 40M steps, but only the best reward parameter RR (w = [1, 1)) was warmed up for 3M steps and fine-tuned for 17M steps later. PG and RND were also trained for 60M steps in order compare with RPGfairly. In Fig. [5] can that PG and RND produced very low rewards because they all converged to non-cooperative policies. w = [1, 1] produced highest rewards after RR, and rewards boosted higher after fine-tuning.
20

---

Published as a conference paper at ICLR 2021
1.2
Original
0.-
Original
tuning
w-[1.1]
w-[1,1]
1.0
[R-10,511]
Fine-tuning
w-(0.5,1]
[=[1,0.]]
w=[1,0.5]
Frequency
Original+RND
Original RND
PST
05
PBT
V Mart
www
62
Steps
Steps
#Split
(b) #Hunt
Original
Original
w=[1]]]
Fine-tuning
w=[1,1]
tuning
[0.5,111
w-[0.5.1]
w=[1,,.5]
w=[1,0.5]
Frequency
Frequency
Original+ RND
0.8
3.5
2.0
Steps
Steps
(c) #Attack
(d) #Cooperate
Original
tuning
w-[ w-[1,1] 1,1]
w=10..51]
N-[10..5)
Rewards
Original RND
PST
Steps
(c) Reward
Figure 15: statistics of standard setting of Agar.o. (a) to (d) illustrate frequencies of Split, Hunt, Attack and Cooperate during training under different reward parameters and algorithms. Splir means catching a script agent ball by splitting, Hunt means catching a script agent ball without splitting, Attack means catching dease-based agent ball, Cooperate means catching script agent ball while the other learn-based agent is close by. same below) (e) illustrates rewards of different policies.
D.2.2 AGGRESSIVE SETTING
We sampled 5 different and their behavior much more various. the other training settings the same as standard setting. in Fig. 16] we should notice that simply sharing reward (w = [1, 1]) didn't 't get very high reward because attacking each other also benefits each other, 2 agents just learned to sacrifice, Again, Fig. iolluustrate that rewards of RPG was far ahead the other policies while both PG and PG+RND failed to learn cooperative strategies.
We also listed all results of Standard and Aggressive setting in Tab. 8 for clearer comparison.
D.2.3 UNIVERSAL REWARD-CONDITIONNS POLICY
We also tried to train a universal policy conditioned on w by randomly sampling different w at the beginning of each episode during training rather than fixing different and training the policy later
21

---

Published as a conference paper at ICLR 2021
w-10.0]
w-[0.0]
w=[0,1]
W
Funi-tuning
30
w-[0,]]
W Fine tuning
w-[1.1]
w-[1.1]
150
W-(0.5.11
w=[0.5.1]
Froquency
125
0.
Original
Orig inal RND
Original+RND
1.03
Population
2.
275
230
0.
62b
Steps
Steps
#Split
(b) #Hunt
w-[0.0]
w-[0.0]
w=[0,]]
Fine-tuning
w=[0;1]
W
Fine tuning
w-[1,1]
w-[1.1]
w=100,5.1]
w=[0.5,1]
Frequency
Original
Frequency
1%-
Original
08
RrD
Original-RND
Population
2.0
Ropulstion
64
05
60
Steps
Steps
(c) #Attack
(d) #Cooperate
w-[9,0]
W Fine-tuning
[0.1]
w=.5.5,11
Rewards
Original
Original
Population
Steps
(e) Reward
Figure 16: Statistics of aggressive setting of Agario. (a) to (d) illustrate frequencies of Split, Hunt, Attack and Cooperate during training under different reward parameters and algorithms.(e illustrates rewards of different policies.
on. But Fig. illustrates, the learning process was very unstable and model performed almost the same under different w due to the intrinsic disadvantage of an on-policy algorithm dealing with multi-tasks: the learning algorithm may pay more effort on w where higher rewards are easier get but ignore the performance on other w, which made it very hard to get diverse behaviors.
D.3 LEARN ADAPTIVE POLICY
In this section, we add the opponents' identity sh in the input of the value network to stable the training process and boost the performance of the adaptive agent. & is a C-dimensional one-hot vector, where C' denotes the number of opponents.
D.3.1 Iterative Stag-Hunt
In Iterative Stag-Hunt, we randomize the payoff matrix, which is 4-dimensional vector, and Cmaz = 4 for sampling w. The parallel threads are 512 and the episode length is 10. Other training hyper-parameter settings are the same Tab Fig 18 describes different
[a, b, c, (i.e.,
22

---

Published as a conference paper at ICLR 2021
0.3
w-[0.01
0.7
w- 0.33
0.32
[0.2
-- 220
0.30
W= [1.1]
Frequency
Frequency
0.3-
004
9.20
0.3
0.35
0.2
0.3
04
2.0
2.0
Steps
Steps
(a) #Split
(b) #Hunt
00_00.0
w=[0,0]
w=100.11
[v-10.1
[1.0]
w- [-110
25
w= [1.13
Frequency
1.50
(1.21
0.50
1.5
3.0
3.5
4.0
4.5
1.5
3.0
2.2
4.5
Sheps
Steps
(c) #Attack
(d) #Cooperate
Figure 17: Statistics of Universal policy of Agario. (a) to (d) illustrate the frequency of Split, Hunt, Attack and Cooperate when fixing different w while evaluating.
Settings
Policy
Rewards
#Split
#Hunt
#Attack
#Cooperate
w=[1,1]
3.843(0.23)
0.859(00083)
0,41 ((0034)
0.526(0.064)
2.203
RPG
1.34(0.171)
0.971
0.659(o.048)
0.548(0.038)
2.028(0.297)
-=
(.827(0.489)
0.807
0.365
(.1500)))))
2.342(0.286)
Standard
[=[1,05]
3.174(0.653)
(.718(0.148))
0.432(0.266)
0.458(0.031)
1.716(0.418)
Original
1.08(0.836)
(.3(0.19)
0.361
0.291 (0.098)
(.443
RND
(.789(0.346)
0.499(a.061)
0.623(o.128)
0.242(0.037)
1.349(0.164)
PBT
3.822(0.347)
0.744<0.12)
0.585(0.146)
(..07)
1.935(0.167)
w=[00.]
5.966(0.539)
(.195(o.155)
(.699(0.008)
0.517
1.603
RPG
(.907(0292))
1.655(0..33)
0.862(0.053)
0.903(0.081)
2.03990.209)
w=10,1]
5.066(0.375)
0.785(0.041)
0.344(0.04))
0.346(0.058)
2.327
w=[1,1]
4.622(0.77)
0.836x0.004)
0.934o.108)
0.552(0.019)
0.028(0.023)
Aggressive
[0.5,1
4.79(0.588)
0.678(0.31)
0.6 (7078)22
(.67(0.194)
(.55(0.643)
Original
3.551
0.7 (7000332)
0.812(0.u78)
0.412(0.018)
0.027(0.066
RND
3.189(0.154)
0.626x0.065)
0.705(0.008)
0.382(0.029)
(.035
PBT
3.348(0.222)
0.697(0.133)
0.732(0.09))
0.396(0.044)
(.007
Table 8: Frequencies of 4 types of events and rewards of different policies of Aganio after completely training.
[4, O, 0, 0j, [o. O. 0, 4], 40,4,44 4, 0). [4, 1, 0) yields different policy profiles. e.g. with w = (0. 0, 0, 4), both agents tend eat the hare. The original game corresponds to w [4, -50, 1]. Tab. reveals w = [4, 0, 0, 0) yields the highest reward and reaches the optimal NE without further fine- finettunigg
Original
[4, 0, 0]
0,, 4]
[0, 4, 4, 0]
w [4, 1,4,,440 -553.45(o.5)
#Rewards
20.00(
74.76(2.88)
20.00(o.00)
-470.(0..00
Table 9: Evaluation different policy profiles obtained via RR in original Iterative Stag-Hunt, Note that [4, 0, 0, 0] has the best performance among the policy profiles, and is the optimal NE with no further fine-tuning.
23

---

Published as a conference paper at ICLR 2021
[1.00000.0]
w=10.0,0,4]
w=[0.4.4.0]
0=(4.000.0
w-(4..14.0)
Frequency
[=
Frequency
Original
-=00.4.4.0]
1,441,4
Original
Episodes
tad
Episodes
145
(a) #Stag- Stag
bb) #Stag-Har Hare
==[4.0.0.0]
[0.00,0,44
==(0.4.4.0
w=[4.1.4.0]
==[4.0.0.0
Original
Frequencc
=-(0.0.0.4)
==(0.4.4.0)
(4..1.44.0)
Original
Episodes
Episodes
145
(c) #Hare-Stag
(d) #Hare-Hare
Figure 18: Find different policy profiles via Reward Randomization in Iterative Stag-Hunt. #Stag- Stag: the frequency of two agents both hunt the stag. "Stag-Hare the frequency of agent1 hunts the stag while agent2 eats the hare. #Hare-Stag: the frequency of agentl eat the hare while agent2 hunts the stag. WHare-Harg the frequency of two agents both the hare. Frequency: times of certain behavior performed in one episode.
Oppo. Type
Stag
Hare
TFT
Random
#Stag
(o.77)
3.6(4.33)
7..1(3.82)
5.35(3.48)
#Hare 0.69(
6.4(4.33)
2.69(3.81)
4.65(3.48)
Table 10: Statistics of the adaptive policy in Iterative Stag-Hunt with 4 hand-designed opponents with different behavior preferences. #Stag: the adaptive agent hunts the stag; #Hare: the adaptive agent eats the hare; The adaptive policy successfully exploits different opponents, including cooperating with TFT opponent, which totally different from trained opponents.
Utilizing 4 different strategies obtained in the RR phase as opponents, we could train an adaptive policy which can make proper decisions according opponent's identity. Fig. 19 shows the adaption training curve, we can see that the policy yields adaptive actions stably after 5e4 episodes. At the evaluation stage, we introduce 4 hand-designed opponents to test the performance of the adaptive policy, including Stag opponent (i.e., always hunt the stag). Hare opponent (i.e., always eat the hare), Tit-for-Tat (TFT) opponent (i.e., always hunt the stag at the first step, and then take the action executed by the other agent the last step), and Random opponent (i.e., randomly choose to hunt the stag or eat the hare at each step). Tab. [00 illustrates that the adaptive policy exploits all sand-designed strategies, including Tit-for-Ta opponent, which significantly differ from the trained opponents.
D.3.2 Monster-Huue Hunt
We use the policy population II, trained by 4 w values (i.e., = 1, = 2, 2,,,2-2,,0 2
[0, 0),w [5, 0, 5)) in the RR phase opponents for training the adaptive policy. In addition,
sample other 4 wo values (i.e., w [5, 0, 0), 5..5. -].. = [-5, 0, 5].w = -5,-5,5 5)) from
Cmer 5 to train opponents for evaluation. Fig. 20 shows the adaption training curve of the
24

---

Published as a conference paper at ICLR 2021
--[4.000.0]
w-[4.,00.01
w [0.0,0011
w=[0,0,0,4]
w=[0.4,4.0]
==[0,4,4.0]
w-(4..14.0
#-[4.1,4,0
Frequency
Frequency
09
Episodes
Episodes
IStag-Stag
(b) #Stag- HStag-Hare
-=[4,0,0.0]
10-
w=[0,0,0.4]
==10,4,4.0
w=[4,1,4.0]
Frequency
Frequency
-4.0..0000
==[0.0.0.4]
[0.44.4440)
-0.14,14,0)
60
06
4.
66
0.6
Episodes
Episodes
(c) #Hare-Stas
(d) Hare
Figure 19: Adaption training curve in Iterative Stag- Hunt. #Stag-Stagy frequency of both agents hunting the stag. #Stag-Haud Hare: frequency agentl hunting the stag while agent2 cating the hare. #Hare-Stag: frequency of agentl cating the hare while agent2 hunting the stag. #Hare- Haree frequency of both agents cating the hare. Frequency: times of certain behavior performed in one episode.
monster-hunt game, where the adaptive policy could take actions stably according to the opponent's identity.
-1.51
m=(5.1.5]
w=15.1.5]
=-14.2:1
m=[42.2]
W-14.2.21
w-10.5.0
-=(0,5.0]
w-10.5.0)
Eptsodes
Eptsodes
(a) #Coop.-Hunt
(b) #Single-Hunt
(c) #Apple
Figure 20: Adaption training statistics of Monster-Huue #Coop.-Hunt: frequency of both agents catching the monster, #Single- Hunt: the adaptive agent meets the monster alone; #Apple: apple frequency.
D.3.3 Agar.io
In Agario, we used 2 types of policies from RR: w [1,0] (i.e. cooperative) and w = 0 1] (i.e. competitive) as opponents, and trained a adaptive policy facing each opponent with probability=50% in standard setting while only its value head could know the opponent's 's type directly. Then we supposed the policy could cooperate compete properly with corresponding opponent. As Fig. 21 illustrates, the adaptive policy learns to cooperate with cooperative partners while avoid being exploited by competitive partners and exploit both partners.
25

---

Published as a conference paper at ICLR 2021
More details about training and evaluating process: Oracle pure- cur-eeoppe policies are learned against a competitive policy for 4e7 steps. So do oracle pure-competitive policies. And the adaptive policy is trained for 6e7 steps. the length of each episode is 350 steps (the half is 175 steps). When evaluating, The policy against the opponent was the adaptive policy first 175 steps whatever we are testing adaptive oracle policies. When we tested adaptive policies, the policy against the opponent would keep going for another 175 steps while the opponent would changed to another type and its hidden state would be emptied to zero. When we tested oracle policies, the policy against the opponent would turn to corresponding oracle policies and the opponent would also changed its type while their hidden states were both emptied.
2.00
compelitive V.s. cooperstive pertner
v.s. compesitive partner
V.5. cooperative partner
120
frequency
0:5
450
4.00
Steps
Steps
(a) #Cooperate
(b) #Attack
Figure 21: Statistics of adaptation experiments of Aganio. (a). illustrate frequencies of Cooperate and Attack when the adaptive policy was facing different partners. (a), we can see that the agent learned to cooperate when the partner was cooperative; In (b), the descend of the "v.s. competitive partner" line the beginning indicates that the adaptive policy was learning to avoid being exploit; The rising of both lines in the end indicates that the adaptive policy was also learning to exploit its partner.
26


Reviews:
[{"review_id": "RYpNArOhv8R", "reviewer": "AnonReviewer4", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper focuses on an important problem, the existence of multiple Nash equilibria in strategic games, and proposes a relatively simple mechanism, reward randomization, which allows agents to discover higher-payoff equilibria in games where normal decentralized policy gradient methods would converge to suboptimal ones. What is proposed is to perturb actual rewards with random perturbations, which essentially, to my mind simply creates a range of games agents find themselves in so that the chances are increased that policy search will end up finding more efficient equilibria. \n\nWhile the overall idea is interesting, the paper actually lacks a precise problem definition that would also link it to the (huge) literature in the area, which it does refer to, but actually not directly compare to, as the now common deep learning route to solving the fundamental (and notoriously hard) problem is applied, which operates in a completely different setting - training function approximators using an enormous number of games played offline. This cannot be compared to the problems considered in game theory and traditional multiagent reinforcement learning, where policies are learned online from a relatively small number of examples, and an algorithm needs to be able to perform well against very broad classes of opponents, without the benefit of training itself on modified problems pre-play.\n\nThat said, I appreciate there is value to the theoretical results that provide some more general evidence for the potential importance of the method. \n\nThe paper makes a lot of assumptions about structure in larger games in order to apply feature-based learning approaches, but one could have approached the whole problem with a simple game and then simply demonstrate how it scales up - it seems like there is not that much to say about the conceptual ideas when one reads all the details. \n\nAn excessive part of the paper is spent on explaining ideas in the stag hunt game and describing the other games, with a lot of further detail included in the lengthy supplementary material, but much of this seems to detail the very specific process of applying the technique and competing alternatives in a few specific games - I don't think much of this adds to our understanding of the problem. \n\nBeyond these criticisms, the paper is generally clearly written, and appears technically sound. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "ItIpu6vELjB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This work proposes and evaluates reward randomization as a strategy to discover efficient policies in multi-agent games. By perturbing the reward structure of a game, the authors show that policy gradient techniques can find better equilibria and lead to complex new behaviors.\n\nReward randomization is a fairly intuitive technique. In matrix form games, this just involves replacing the game's rewards with those drawn from some distribution. In more complex games, the authors propose distilling the game's reward structure into a small number of components and randomizing the weights placed on those components to compute the total payoff. The authors demonstrate that both theoretically and empirically, Reward-randomized Policy Gradient (RPG) outperforms standard baseline techniques. It also produces a diverse set of candidate policies, which the authors demonstrate can be used to train an adaptive agent.\n\nThe paper is clear and well-written. The figures are helpful and detailed. Overall, my impression is positive.\n\nSome analysis of the sensitivity of this method would have helped. Much of the complexity is folded into choosing an appropriate reward distribution, and it would be good to know how dependent the results are on being able to choose a \"good\" distribution from which to sample.\n\nI would have appreciated more of a discussion about why reward randomization works. Fundamentally, this appears to rely on the idea that while the action space may in general be very large, for most natural games, there are no reasonable reward schemes that incentivize the vast majority of these behaviors. As a result, it is feasible to explore the space of potentially optimal policies simply by exploring the space of reasonable rewards. Can this statement be formalized? And how well does it generalize to games other than the ones considered?", "extra_scores": {}, "extra_text": {}}, {"review_id": "EqTICpIKFnt", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper considers the problem of finding a nash equilibrium in two player games where each of the algorithm runs an RL algorithm. In this paper they ask the question -- which nash equilibria does the dynamics converge to in this two player game (where each player optimizes based on a policy gradient algorithm). They construct two player games with multiple nash equilibria; one is a favorable nash equilibria where both players get high rewards while the other is a less favorable nash equilibria where both player only get medium rewards. In such games they first show that in general simply running policy gradient on the natural reward function i.e., the observed payoff will not lead to the desirable nash equilibria. The goal of this paper is to ameliorate this by considering perturbations in the reward space. At a high level, the algorithm learns multiple policies on a class of games generated by sampling multiple reward functions from a family and training one policy per sampled reward function using PG. Then using an evaluation function, the best policy is picked by evaluating each of the learnt policies on the original game.\n\nMy comments on this paper are as follows. First, I think the question studied in this paper is well-motivated. In general, controlling for which nash equilibrium a two player (or N-player in general) dynamics should converge to is an important problem. This problem has been extensively considered in the game theory and online learning literature. So the importance naturally extends to the multi-agent RL world. The proposed algorithm here is reminiscent of follow-the-perturbed-leader, where perturbations in the reward space (as opposed to the policy space) leads to improved algorithms. The strengths of this paper are as follows. \n\n- The initial parts of the paper are well-written. They consider simple toy examples to show that PG can indeed lead to bad equilibria. Then using some stylized analysis, show that sampling from the reward space can indeed overcome this problem (in games where the family of reward functions for which PG converges to the desired nash equilibria is large, yet for the specific game at hand PG leads to a bad equilibria).\n- Extensive experimental evaluation. The paper considers a total of four test bed games and shows the benefit of using reward randomization in these settings.  In the supplementary materials there is extensive simulated results on these games. In particular, they fix a particular \"true\" payoff matrix and then run their algorithm against a few baselines assuming this game.\n- The problem considered is important, not just in the artificial game setting but also in many practical applications which can be modeled as a game that ends up having multiple NE.\n- Specification of the hyper-parameters of the algorithm used. Also evaluating the algorithms using multiple seeds (which is an important criteria for RL algorithms).\n\nHaving said that, here are some of the weakness of this paper.\n\n- The considered algorithm \"works\" probably because the settings are easy (As defined by convergence to the correct NE by PG algorithms) for an average instance from the space of all instances. In particular, consider the following thought exercise. Let us sample a random payoff matrix from the space of payoffs and run PG on this game. What is the prob. that PG will get stuck at the bad NE? If the answer is that this prob. is high, then it is also likely that the proposed algorithm will not work (since this is essentially the idea being exploited in the algorithm). On the other hand, if the prob. is low then it shows that in general the considered game is easy and this algorithm only optimizes for the \"outlier\" scenarios. In general, that is the biggest weakness I see in this paper; it makes a pretty strong implicit structural assumption on the games and their corresponding payoff landscape. Am I missing something here?\n- I also think this paper could improve its presentation. First, the experimental setup is pretty unclear. What is the reward function in each of the games. I do not see a formal definition. Likewise, the algorithm description itself is pretty informal. It takes a bit of leap of faith in assuming that there exists a well-defined evaluation function (that is computable). It would greatly help the paper in readability if things are written in a formal manner. Moreover, for each of the games (possibly in supplementary) taking a detailed approach to the setup of the game, the reward function and the evaluation function would help in reproducibility and understanding of this paper. Finally, I also think some of the graphs could use better color-schemes or other differentiating factors apart from color. Some of the colors are pretty close to each other and in general harder to read.\n\nMy overall evaluation is based on the first point in my weakness section and considering the paper in totality. If the authors can sufficiently answer that question and show convincing experiments and/or explanation I am willing to change my score.", "extra_scores": {}, "extra_text": {}}, {"review_id": "4qMNkRZoZWj", "reviewer": "AnonReviewer3", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes to use reward randomization to explore the policy space in multi-agent games. The idea is that in most of multi-agent games multiple Nash Equilibriums exist with different payoffs. The goal is to find the NE that provides the highest payoff. \nPolicy Gradient and its variants, which have obtained a lot of practical successes, in general fail to find the NE with the highest payoff. \nA first approach could be to re-start PG with different initializations for finding different NEs and then selects the best one. \nIn contrast, the authors propose to randomize the reward structure for exploring different policies. Then the policies are optimized on different reward structures with PG. The policy that leads to the highest payoff is selected and then optimized with PG on the original structure of rewards.\nThe authors provide some theoretical results to show that reward randomization has a highest probability to find the best NE than random initializations of PG. \nThe authors also propose to use reward randomization for learning an agent against different type of opponents. \nThe experiments are done on three games and show the interest of their approach in comparison with several baselines.\n\nThe paper is well written, proposes interesting ideas supported by analytical and experimental results. However the reviewer has some remarks, concerns and questions.\n\nConcerning Theorem 1, O(\\epsilon) for a probability is not a strong result: it can be higher than 1. After looking the proof, the reviewer thinks that it seems possible to provide the right expression of the probability of finding the high payoff NE. \n\nConcerning Theorem 2, the proof is quite informal and the reviewer is not sure that it is correct. In particular, it is not clear if the same condition than in Theorem 1 is necessary: a-b = \\epsilon (d-c). In the statement it seems not because a,b,c,d are uniformly sampled and there is no \\epsilon in the statement, but the remark stating that RR necessitates at most O(\\log1/\\epsilon) times to achieves 1-\\epsilon suggests that it does. \nMoreover the reviewer thinks that the proposed analysis (statements of Theorem 1 and 2) will be more convincing if the number of starts, needed by the two approaches for finding w.h.p the high payoff NE, is compared (as you did in the remark).\n\nIn Algorithm 2, the authors write that the policy \\pi’_2 is drawn from \\Pi_2, but in the experiments section 5.3, the authors explain that \\Pi_2 is carefully built, meaning that the policies in \\Pi are chosen to be effective. This step is not in Algorithm 2, which is still correct, but this suggests that if \\Pi_2 is not well chosen Algorithm 2 does not work.\nThis leads to my main concern. The rewards seem to be uniformly sampled with the constraint that their sum is no more than C_{max}. However, with this kind of uniform sampling the set of games used for exploring policies contains a lot of games that does not respect the constraints induced by the original game M. For instance in stag-hunt we have a \\geq b \\geq d > c. Using uniform sampling most of the induced games do not respect this reward structure. So it can lead to inefficient policy. For instance if a < b and a < d an efficient policy is to not track the stag and to hunt the hare. The reviewer understands that the diversity of rewards allows the diversity of obtained policies, but the reviewer is wondering if sampling the rewards with respect to the reward constraints of the game is not enough to obtain the diversity of policies. At a minimum, it could be interesting for the reader to have this reasonable baseline. By the way, may be this baseline allows Algorithm 2 working without carefully choosing the set of policies \\Pi.\n\nOverall, the paper is interesting, but the reviewer thinks that it could be better. The reviewer can change his mind if his concerns are answered.\n\n\n___________________________\n\n\nAfter the rebuttal I raised my score.\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: All the reviewers are in favor of accepting this paper, which demonstrates both theoretically and empirically the value of reward randomization in solving multi-agent reinforcement learning problems. The rebuttal phase was crucial in improving the quality and evaluation of the submission. I am glad to recommend acceptance.
Decision: Accept (Poster)