Truthful Self-Play
Authors: Shohei Ohsawa
Venue:  (2021)
Keywords: Comm-POSG
Imaginary Rewards

Abstract: We present a general framework for evolutionary learning to emergent unbiased state representation without any supervision. Evolutionary frameworks such as self-play converge to bad local optima in case of multi-agent reinforcement learning in non-cooperative partially observable environments with communication due to information asymmetry.  Our proposed framework is a simple modification of self-play inspired by mechanism design, also known as {\em reverse game theory}, to elicit truthful signals and make the agents cooperative. The key idea is to add imaginary rewards using the peer prediction method, i.e., a mechanism for evaluating the validity of information exchanged between agents in a decentralized environment. Numerical experiments with predator prey, traffic junction and StarCraft tasks demonstrate that the state-of-the-art performance of our framework.


Under review as a conference paper at ICLR 2021
TRUTHFUL SELF-PLAY
Anonymous authors Paper under double-blind review
ABSTRACT
We present a general framework for evolutionary learning to emergent unbiased state representation without any supervision. Evolutionary frameworks such self-play converge to bad local optima case of multi-agent reinforcement learning in non-cooperative partially observable environments with communication due information asymmetry. Our proposed framework is a simple modification of self- play inspired by mechanism design, also known as reverse game theory, to elicit truthful signals and make the agents cooperative. The key idea is to add imaginary rewards using the peer prediction method, i.e., a mechanism for evaluating the validity of information exchanged between agents in a decentralized environment. Numerical experiments with predator prey, traffic junction and StarCraft tasks demonstrate that the state-of-the-art performance of our framework.
INTRODUCTION
Evolving culture prevents deep neural networks from falling into bad local optima (Bengio, 2012). For example, self-play (Samuel, 1967; Tesauro, 1995) has not only demonstrated the ability to abstract high-dimensional state spaces as typified by AlphaGoo (Silver et al., 2017), but also improved exploration coverage in partially observable environments and communication (Sukhbaatar al., 2016; Singh et al., 2019) to exchange their internal representations, such as explored observation and hidden state in RNNs. Evolutionary learning is expected be a general framework for creating superhuman AIs as such learning can generate a high-level abstract representation without any bias in supervision.
However, when applying evolutionary learning to a partially observable environment with non- cooperative agents, improper bias is injected into the state representation. This bias originates from the environment. A partially observable environment with non-cooperative agents induces actions that disable an agent from honestly sharing the correct internal state resulting in the agent taking actions such as concealing information and deceiving other agents at equilibrium (Singh et al., 2019). The problem arises because the agent cannot fully observe the state the environment, and thus, does not have sufficient knowledge verify the information provided by other agents. Furthermore, neural networks are vulnerable to adversarial examples (Szegedy et al., 2014) and are likely to induce erroneous behavior with small perturbations. Many discriminative models for information accuracy are available; these include GANs (Goodfellow et al., 2014; Radford et al., 2016) and curriculum learning (Lowe al., 2020). However, these models assume that accurate samples can be obtained by supervision. Because of this assumption, is it impossible to apply these models to a partially observable environment, where the distribution is not stable.
We generalize self self-play to non-cooperative partially observable environments via mechanism design (Myerson, 1983; Miller al., 2005), which also known as reverse game theory. The key idea is to add imaginary rewards by using the peer prediction method (Miller et al., 2005), that is, mechanism for evaluating the validity of information exchanged between agents in decentralized environment, which is calculated based social influence the signals. We formulate the non-cooperative partially observable environment as an extention of the pertially observable stochastic games (POSG) (Hansen al., 2004); introduce truthfulness (Vickrey. 1961), which is an indicator of the validity of state representation. We show that the imaginary reward enables us to reflect the bias of state representation on the gradient without oracles.
As the first contribution, we propose truthful self-play (TSP) and analytically demonstrate convergence to the global optimum (Section 4). We propose the imaginary reward on the basis of the peer prediction

---

Under review as a conference paper at ICLR 2021
method (Miller et al., 2005) and apply it to self- The mechanism affects the gradient of the local optima, but not the global optima. The trick is to use the actions taken by the agents as feedback to verify the received signal from the every other agent, instead of the true state, imput, and intent, which the agents cannot fully observe. TSP only requires a modification of the baseline function for self-play; it drastically improves the convergence to the global optimum in Comm-POSG.
As the second contribution, based on the results of numerical experiments, we report that the TSP achieved state-of-the-art performance for various multi-agent tasks made of up to 20 agents (Section 5). Using predator prey (Barrett et al., 2011), traffic junction (Sukhbaatar et al., 2016; Singh et al., 2019), and StarCraft Synnaeve al. (2016) environments, which are typically used in Comm- POSG research, we compared the performances of TSP with the current neural nets, including the state-of- the-art method, with LSTM, CommNet (Sukhbaatar et al., 2016), and IC3Net (Singh et al., 2019). We report that the model with IC3Net optimized by TSP has the best performance.
This work the first attempt to apply mechanism design to evolutionary learning. TSP is a general optimization algorithm whose convergence is theoretically guaranteed for arbitrary policies and environments. Furthermore, since no supervision is required, TSP has a wide range of applications to not only game AIs (Silver et al., 2017), but also the robots (Jaderberg et al., 2018), chatbots (Gupta et al., 2019; Chevalier et al., 2019), and autonomous cars (Tang, 2019) that are employed in multiagent tasks.
Notation: Vectors are columns. Let [n]] := [l..... n). I is a set of real numbers. is the imaginary unit. Re and Im u a real and an imaginary part of complex number u, respectively. n-tuple are written as boldface of the original variables a == (a1..... an) and a is a (n 1) 1t-uee obtained by removing the i-th entry from a. Let 1 == (l,..., 1)T. Matrices are shown in uppercase letters L = (Laj). E is the unit matrix. The set of probability distributions based on the support X is described as ((X).
2 RELATED WORK
Neural communication has gained attention in the field of multiagent reinforcement learning (MARL) for both discrete (Foerster et al., 2016) and continuous (Sukhbaatar et al., 2016; Singh et al., 2019) signals. Those networks are trained via self-play to exchange the internal state of the environment stored in the working memory of recurrent neural networks (RNNs) to learn the right policy in partially observable environments.
The term self-play was coined by the game Al community in the latter half of the century. Samuel (Samuel, 1967) introduced self-play as a framework for sharing state-action value among two opposing agents to efficiently search the state space at Checkers. TD-Gammon (Tesauro. 1995) introduced self-play as a framework to learn TD(A) (Sutton & Barto, 1998) and achieve professional- grade levels in backgammon. AlphaGo (Silver et al., 2017) defeated the Go champion by combining supervised learning with professional game records and self-play. AlphaZero (Silver et al., 2018) successfully learnt beyond its own performance entirely based on self-play. All these studies explain that climinating the bias of human knowledge in supervision is the advantage of self-play.
Self-play also known as evolutionary learning (Bengio, 2012) in the deep learning community mainly as an approach to emerging representations without supervision (Bansal et al., 2018; Balduzzi al., 2019). Bansal al. (2018) show that competitive environments contribute to emerging diversity and complexity. Rich generative models such as GANs (Goodfellow et al., 2014; Radford et al., 2016) are frameworks for acquiring an environmental model by employing competitive settings. RNNs such as world models (Ha & Schmidhuber, 2018; Eslami et al., 2018) are capable of more comprehensive ranges of exploration in partially observable environments and generation of symbols and languages (Bengio, 2017; Gupta et al., 2019; Chevalier et al., 2019). The difference between cvolutionary learning and supervised learning is the absence of human knowledge and oracles.
Several works have formalized those in which the agents exchange environmental information as a formal class of the games such as Dec- Piee-POMPPCoom (Goldman & Zilberstein, 2003) and COM- MTDP (Pynadath & Tambe, 2002), and several frameworks are proposed to aim to solve the problems. However, the limitation of the frameworks is that they assume a common reward. As there are yet no formal definition of non-cooperative communication game, we formalize such a game to
2

---

Under review as a conference paper at ICLR 2021
Comm-POSG as superset of POSGs (Hansen et al., 2004), games including the cases of non-cooperativity (Hansen et al., 2004).
general class of multi- -agett
To the best of our knowledge, there field of MARL, but it may be possible to introduce it by using agents that can learn flexibly, such as neural networks. A typical truthful mechanism is the VCG mechanism (Vickrey, 1961), which is generalization of the pivot method used in auction theory, but whereas the subject of the report that must satisfy truthfulness must be a valuation (or value function if interpreted from RL perspective). In this study, the scope of application is different because the belief states of the environment are subject to reporting. Therefore, we introduce instead peer prediction method (Miller al., 2005) that guarantees truthfulness with respect to reporting beliefs about arbitrary probability distributions using proper scoring rules (Gneiting & Raftery, 2007).
studies that have introduced truthful mechanisms into the
PROBLEM DEFINITION
3.1
COMM-POSG
stochastic game (Comm-POSCI is a class of coopperree Bayesian games in which every agent does fully observe the environment but interacts each other. We define Comm-POSG as an extension of POSG (Hansen et al., 2004) with a message protocol.
communicative
Definition 3.1 (Hansen al., 2004) POSG (n, A, T, P, R) is class for multi-agent decision making under uncertainty in which the state evolves over time 1 S S T, where
is the number of agents,
T is a horizon i.c., the episode length,
S is set of discrete/continuouss state 8, E S with an initial probabilistic distribution p(50).
A is a set of discrete/comtinuous action as E A.
is a set discrete/continuous observation Tu E X,
* T P (S x X S) is state transition probability,
. P E P (S x x²) is an observation probability, and R: A R. is reward function that outputs n-ddiennsioall vector.
In Comm-POSGs, every agent further follows a message protocol gaxx, where is the dis- crete/continuous signal space. The complete information exchanged among the agent in time is Z., where Z, := (znij) signal from Agent an internal state of i-th agent before receiving the singals from the others. A game in Comm-POSC is denoted as G (n. T, S, A, X, T, R, Z).
E znxn is a signal matrix in which (i,j)-th entry Zrij represents a Agent at l. The i-th diagonal entry of Ze, hui == Zuū represents the pre-state,
The objective function of Comm- is social welfare (Arrow, 1963) defined by the following,
T
J
V : E
(1)
where 7 1] is discount rate, is reward Ti is a stochastic policy, and V is the value function.
In extensive-form games including Comm-POSC, in addition to the information in the environment, the information of other agents cannot be observed. In the optimization problem under these assump-
tions, policy converges a solution called the Bayesian Nash equilibrium (BNE) (Fudenberg, 1993). We denote the social welfare at the BNE is J and the global maximum J. general, J + holds, which is closely related to the information asymmetry.
3.2 COMMUNICATIVE RECURRENT AGENTS
In order to propose an optimization algorithm in this paper, we do not propose a concrete structure of the network, but we propose abstract structure that can cover existing neural communication models (Sukhbaatar et al., 2016; Singh et al., 2019), namely communicative recurrent agents (CRAs)
(Ser Jo. Jø, no), where
3

---

Under review as a conference paper at ICLR 2021
fo(he-1,, + Z is deep RNN for the high- nigh-dimensional imput Tui X and the previous post-state h E 2, with parameter and an initial state hg E Z, Po(zeilee) is stochastic messaging policy for pre-state hy ==
Tti),
qo(nu k is stochastic model for a post-state his E 2 and the received messages Zn := Z (2116 1,,5-1,6, het, 2t,i+1, ,...,,.................. Atns) and
xo(au has) is the stochastic action policy with a parameter
These agents are trained through self-play using on-policy learning such as REINFORCE (Williams, 1992). All n-agents share the same weight per episode, and the weights updated based on the cumulative reward after the episode.
In addition to the recurrent agent's 's output of actions with the observation series as input, the CRA has signals for communication as input and output. CRAs estimate current state of the environment and current value of the agent herself based on the post-state model with the pre-state h4 the hidden layer of the RNN and the received signals 2 from other agents. Hence, the veracity of the signals Zu is the point of contention.
3.3 TRUTHFULNESS
In mechanism design, a truthfuul game (Vickrey, 1961) is game in which all agents make an honest reporting in the Bayesian Nash equilibrium. In POSms, the truthfulness of the game is achieved if all the sent signal equals the pre-state žtij has i.e. all the agent share complete information. In such case, all the agents can have the same information 2ns h, := (hei..... hee)) for all i's. In such a case, all agents will have the same post-state model probability distribution and the mean of the cross entropy between the probability distributions of each model will be minimized.
Σ T2
H
(he (2x)
ΣE DKL (ao(helau)) (o(ll
The first term represents the entropy of knowledge each agent has about the environment, and the second term represents the information asymmetry between agents; D& is a lower bound on the amount of true information the environment has, HH [p(s:)] ()]]: since achieving truthfulness essentially the same problem minimizing D&, eventually it also maximizes J will be maximized. Proposition 3.1. (global optimally) For any games in Comm-POSG, if (z. H [p(s:)),orr 0 S t < T and R2 is symmetric for any permutation of E [n]]. (g) j(G) holds'.
PROPOSED FRAMEWORK
An obvious way to achieve truthful learning is to add D& as penalty term of the objective, but there are two obstacles to this approach. One is that the new regularization term also adds a bias to the social welfare J, and the other is that D, contains the agent's internal state, post-state hes so the exact amount cannot be measured by the designer of the learner: If post-states reported correctly, then pre-states should also be reported honestly, and thus truthfulness is achieved. Therefore, it must be assumed that the post-states cannot be observed during optimization.
Our framework, truthful self-play (TSP), consists of two elements: one is the introduction of imaginary rewards, general framework for unbiased regularization in Comm-POSG, and the other is the introduction of peer prediction method (Miller et al., 2005), truthful mechanism to encourage honest reporting based solely on observable variables. In the following, each them is described separately and we clarify that the proposed framework converges to the global optimum in Comm-POSG. We show the whole procedure in Algorithm 1.
4.1 IMAGINARY REWARD
Imaginary rewards are virtual rewards passed from an agent and have a different basis i than rewards passed from the environment, with the characteristic that they sum to zero. Since the most of RL
Refer Section for the pronfs.
4

---

Under review as a conference paper at ICLR 2021
Algorithm 1 The truthful self-play (TSP).
Require: Comm-POSG
2), CRA (fos oø. 4s. To) with initial weight Wo = (60, Φo) and initial state ho. learning rate >> O, and mass parameter / 2 0.
Initialize w <- Wo-
for each episode do Genesis: $1 ~ p(s), hos + ho, Vi E [n]]
for = 1 to T do
1. Self-Play
Observe
Xt ~ P(-)8e).
Update pre-state
hu + fol fo Dti,,
e [n]
Generate message
Zei a (-1he))
Vi [
Send message
Ze t (211.... Zend.
Receive the message
Zei + Z
we [r]
Update post-state
his (112))))
e [n]
Act
TT( hes). re f- R(s,, a,).
vi [n]
Get the real reward
2. Compute score matrix C, with the peer prediction mechanism,
Lig {o
log To (au(lz))))
(i j)=
Vi,j [n]
(3)
3. Combine the real and imaginary rewards,
R + R +iC
(4)
4. Update the weights by policy gradient (Williams, 1992).
Vw
log (are (hs) + log go (hri (e:) + log 0o (o (ze 1,5,
tjo
1=1
)=1
W - w + aReg: g:
+ a:3Im gr.
(5)
5. Proceed to the next state 8t-1 T(-18%, ar).
end for end for return
environments, including Comm-POSC, are of no other entities than agent and environment, two- dimensional structure are sufficient to describe them comprehensively if we wish to distinguish the sender of the reward. To remain the social welfare of the system is real, the system must be designed so that the sum of the imaginary rewards, i.e., imaginary part of the social welfare, is zero. In other words, it is not observed macroscopically and affects only the relative expected rewards of agents. The real and imaginary parts of the complex rewards ordered by the mass parameter | during training, which allows the weights of the network to maintain a real structure.
The whole imaginary reward is d +Y (EE() where ły; is the imaginary reward passed from Agent i to Agent j, and the complex reward for the whole game is R R iY where is a diagonal matrix with the environmental reward r, as (i, i)-th entry. We write GliY) as the structure in which this structure is introduced. In this case, the following proposition holds.
Proposition 4.1. For any G in Comm-POSG. if G(EY] is truthfull and R is Hermitian matrix, ("liYY)] ((] holds.
Proof. Since G[iY] truthful, (G Y(g holds from Proposition 3.1. Further, since R is Hermitian, رyز = - enzo and hence Im (G 0 holds; jgl(Y)) -(G) holds. D
Note the of for imaginary units and for indices.

---

Under review as a conference paper at ICLR 2021
This indicates that (YY) 2 ()) indicating that the BNE could be improved by introducing imaginary rewards. Also, since Σi=1 E 2z/4 = from the condition that R is Hermitian, the imaginary rewards do not affect the social welfare of the system, which is a macroscopic objective function, but only the expected rewards of each agent. The bascline function in policy gradient Williams (1992) is an example of a function that does not affect the objective function when the mean gets zero. However, the baseline function is quantity that is determined based on the value function of a single agent, whereas the imaginary reward is different in that (1) it affects the value function of each agent and (2) it is meaningful quantity only when n 2 2 and is not observed when n
4.2 PEER PREDICTION MECHANISM
The peer prediction mechanism (Miller et al., 2005) is derived from a mechanism design using proper scoring rules (Gneiting & Raftery, 2007), which aims to encourage verifiers to honestly report their beliefs by assigning reward measure score to their responses when predicting probabilistic events. These mechanisms assume at least two agents, a reporter and a verifier.
The general scoring rule can be expressed as F(pells) where ps is the probability of occurrence reported by the verifier for the event s, and F(p, [s] is the score to be obtained if the reported event s actually occurred. The scoring rule is proper if honest declaration consistent with the beliefs of the verifier and the reported Pa maximizes the expected value of the earned score, and it is strictly proper if it is the only option for maximizing the expected value. A representative example that strictly proper is the logarithmic scoring rule F(pe (Is) = log Ps. where the expected value for a 1-bit signal the cross-entropy P lo + (1 (1-P3) log(1 ps) for belief p One can find that pa P the only report that maximizes the score.
Since the proper scoring rule assumes that events s are observable, it is not applicable to problems such as partial observation environments where the true value is hidden. Miller et al. (2005), who first presented peer prediction mechanism, posed scoring to a posterior of the verifiers that are updated by the signal, rather than the event. This concept is formulated by a model that assumes that an event s emits a signal z stochastically and infers the type of s by the signal of the reporters who receive The peer prediction mechanism (Miller et al., 2005) is denoted as F(p(s(z)]]) under the assumption that (1) the type of event s and the signal æ emitted by each type follow a given prior, (2) the priors are shared knowledge among verifiers, and (3) the posterior is updated according to the reports.
We apply the mechanism to RL, i.e., the problem of predicting the agent's optimal behavior aes ~ Tols; for the true state 8 S. In self- self-play, the conditions of 1 and 2 can be satisfied because the prior Ty is shared among the agents, and furthermore, the post-state in Comm-POSE corresponds to so that the peer prediction mechanism can be applied to the problem of predicting agent behavior. To summarize the above discussion, we can see that we can allocate a score matrix L, as follows,
L. = (f(ar) Reji) (e))))))))) )ii.je ((anlze)) == ((r [|axs) = log no Ta (2g3),
(6)
which is an n-order square matrix representing the score from Agent to Agent j.
4.3 THE TRUTHFUL SELF-PLAY
In our framework, truthful mechanism is constructed by introducing the proper prediction mecha- nism into imaginary rewards. Since the score matrix L, does not satisfy Hermitianity, we perform zero-averaging by subtracting the mean of the scores from each element of the matrix, thereby making the sum to zero. This can be expressed as follows using the graph Laplacian A == E 11 TIT/m /n_
n
-1
n-1
n
-i
-1
E(an
((ar2)
Elaen Fein) E(asn Ziza
Y, = AL.
=
n2
n-1
((aalZznz) M(ara(Zenz)
to get
R = R, iAC.
(8)
which is the formula that connects reinforcement learning and mechanism design.

---

Under review as a conference paper at ICLR 2021
Theorem 4.1. (global optinally) For any games in Comm-POSG, TSP converges the global optinum J the following convergence condition met,
Re V
sup
< 3
(9)
ml V
where B 0o bounded mass parameter.
Proof (in summary.) R iAC is Hermitian; and if Eq (9) holds, then G[iAC] is truthful from Proposition A.3. Therefore, from Proposition 4.1, convergence to the global optima achieved.
NUMERICAL EXPERIMENT
In this section, we establish the convergence of TSP through the results of numerical experiments with deep neural nets. We consider three environments for our analysis and experiments (-> Fig. 1). (a) a predator prey environment (PP) which predators with limited vision look for a prey on square grid. (b) traffic junction environment (TJ) similar to Sukhbaatar et al. (2016) in which agents with limited vision learn to signal in order to avoid collisions. (c) StarCraft: Brood Wars (SC) explore and combat tasks which test control on multiple agents in various scenarios where agent needs to understand and decouple observations for multiple opposing units.
Visual range
Visuil range
3 possible
New anrivals
rouites
Friend
Enemy
Preduter
Viuaal
Car exiingg
Figure 1: Experimental environments. Predator Prey (PP-n) (Barrett al., 2011). Each agent receives rıa -0.05 at each time step. After reaching the prey, they receive t&s = 1/m, where m the number predators that have reached the prey. b: Traffic Junction (TJ-n) (Sukhbaatar et al., 2016; Singh et al., 2019). n cars with limited sight inform the other cars of each position to avoid collision. The cars continue to receive a reward of Ft: -0.05 at each time as an incentive to run faster. If cars collide, each car involved in the collision will receive StarCraft: Blood Wars (SC) (Synnaeve al., 2016).
-1 c: Combat task in
We compare the performances of TSP with self-play (SP) and SP with curiosity (Houthooft et al., 2016) using three tasks belonging to Comm-POSG. comprising up 20 agents. The hyperparameters are listed in the appendix. With regard CRAs. three models namely LSTM, CommNet (Sukhbaatar al., 2016), and IC3Net (Singh et al., 2019), were compared. The empirical mean of the social welfare function J was used as a measure for the comparison. IC3Net is an improvement over CommNet, which is continuous communication method based on LSTM. Actor-critic and value functions were added to the baselines in all the frameworks. We performed 2,000 epochs of experiment with 500 steps, each using 120 CPUs; the experiment was conducted over a period of three days.
PP and TJ: Table 1 lists the experimental results for each task. We can see that IC3Net with TSP outperforms the one with for all tasks. Fig. (a) shows that TSP elicits truthful information, and (b) confirms that the social welfare of TSP exceeds that of the SPs. (c) confirms that the average of the imaginary part is zero. From these experimental results, we conclude that the TSP successfully realized truthful learning and tfate-of-the-arr art in tasks comprising 3 to 20 agents.
StarCraft: Table 2 shows a comparison of social welfare in the exploration and combat tasks in StarCraft. (i) In the search task, 10 Medics find one enemy medic 50-cll grid; similar to PP, the reward is a competitive task where the reward divided by the number of medics found. (ii) In the combat task, 10 Marines versus 3 Zealots fight 50x cell grid. The maximum step of the
7

---

Under review as a conference paper at ICLR 2021
Table I: Social welfare J in five Comm-POSG tasks. PP-n: Predator prey and TJ-n: Traffic junction. All the scores are negatives. The experiment was repeated thrice. The average and standard deviation listed. Bold is the highest score. The models listed the top three rows show the models optimized by SP, and the bottom row shows IC3Net optimized by TSP.
PP-3
PP-5
TJ-5
TJ-10
TJ-20
SP
LSTM
1.92 + 0.35
4.97
1.33
22.32
1.04
47.91
41.2
819.97 + 438.7
CommNet
1.54 + 0.33
4.30
+ 1.14
6.86
= 6.43
26.63
4.56
463.91 + 460.8
IC3Net
1.03 + 0.06
2.44
0.18
4.35
0.72
17.54
6.44
216.31 + 131.7
TSP
IC3Net
0.69 + 0.14
2.34
0.21
3.93
1.46
12.83
2.50
132.60 + 17.91
0200
play
66025
-000
00
1400
200 1482
200
1006
1400
Figure 2: Learning curves in three-agent predator prey (PP-3). Truthfulness, the fraction of steps that the agent shares a true pre-state (Zij = h:), b the real part of the reward, and e the imaginary part.
Table 2:
StarCraft Results: TSP beats the baselines. The experiment was repeated thrice. All the scores are negatives. The average and standard deviation are listed. Bold the highest score.
StarCraft task
CommNet
IC3Net
IC3Net w/ TSP
Explore- 10Medic 50x50
1.592 0.169
2.276 + 1.427
1.364 + 0.107
Combat-10My32 50x50
3,202 + 1.382
3.815 = 0.392
1.717 + 1.548
episode is set at 60. We find that IC3Net, with its information-hiding gate, performs less well than CommNet but performs better when trained in TSP due to the truthful mechanism.
CONCLUDING REMARK
Our objective construct general framework for emergent unbiased state representation without any supervision. Firstly, we proposed the TSP and theoretically clarified its convergence the global optimum in the general case. Secondly, we performed experiments involving up to 20 agents and achieved the statc-of-the-as performance for all the tasks. Herein, we summarize the advantages of our framework.
1. Strong convergence: TSP guarantees convergence the global optimum theoretically and experimentally; self-play cannot provide such a guarantee. Besides, the imaginary reward iAC satisfies the baseline condition.
2. Simple solution:
The only modification required for TSP is that iAC should be added to the baseline in order to easily implement for deep learning software libraries such as TensorFlow and PyTorch.
3. Broad coverage: TSP is general framework, the same as self-play, Since TSP is indepen- dent of both agents and environments and supports both discrete and continuous control, can be applied to wide range of domains. No supervision is required.
To the best of our knowledge, introducing mechanism design to MARL is new direction for the deep-learning community, In future work, we will consider fairness (Sen, 1984) the social choice function. We expect that many other frameworks will be developed by using the methodology employed in this study.
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
Kenneth J Arrow. Social choice and individual values. Yale university press, 1963.
David Balduzzi, Marta Garnelo, Yoram Bachrach, Wojciech M Czarnecki, Julien Perolat, Max Jaderberg, and Thore Graepel. Open-ended learning in symmetric zero-sum games. ICML, 2019.
Trapit Bansal, Jakub Pachocki, Szymon Sidor, Ilya Sutskever, and Igor Mordatch. Emergent com- plexity via multi- aggent competition. ICLR, 2018.
Samuel Barrett, Peter Stone, and Sarit Kraus, Empirical evaluation of ad hoc teamwork in the pursuit domain. In AAMAS, 2011.
Yoshua Bengio. Evolving culture vs local minima. arxiv: 1203.29900 2012.
Yoshua Bengio. The consciousness prior. arXiv: 085688 2017.
Lev M Bregman. The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming. USSR computational mathematics and mathematical physics, 7(3):200-217, 1967.
Glenn W Brier. Verification of forecasts expressed terms of probability. Monthly weather review, 78(1):1-3, 1950.
Maxime Chevalier, Dzmitry Bahdanau, Salem Lahlou, Lucas Willems, Chitwan Saharia, Thien Huu Nguyen, and Yoshua Bengio. BabyAl: First steps towards grounded language learning with human in the loop. In ICLR, 2019.
SM Ali Eslami, Danilo Jimenez Rezende, Frederic Besse, Fabio Viola, Ari S Morcos, Marta Gar- nelo, Avraham Ruderman, Andrei A Rusu, Ivo Danihelka, Karol Gregor, et al. Neural scene representation and rendering. Science, 36066394):1204-1210, 2018.
Jakob Foerster, Yannis Assael, Nando de Freitas, and Shimon Whiteson. Learning to communicate with deep multi-agent reinforcement learning. In NIPS, 2016.
Drew Fudenberg. Game theory. MIT Press, 1993.
Tilmann Gneiting and Adrian E Raftery. Strictly proper scoring rules, prediction, and estimation. Journal of the American Statistical Association, 102(477):359-378 2007.
Claudia V Goldman and Shlomo Zilberstein. Optimizing information exchange in cooperative multi-agent systems. In Proceedings of the second international joint conference on Autonomous agents and multiagent systems, pp. 137-144, 2003.
Irving John Good. Rational decisions. In Breakthroughs in statistics, pp. 365-377. Springer, 1952.
Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In NIPS, 2014.
Abhinav Gupta, Ryan Lowe, Jakob Foerster, Douwe Kiela, and Joelle Pineau. Seeded self-play for language learning. In Proceedings of the beyond vision and language: integrating real-world knowledge, 2019.
David Ha and Jürgen Schmidhuber. World models. 18X3 2018.
Eric A Hansen, Daniel S Bernstein, and Shlomo Zilberstein. Dynamic programming for partially observable stochastic games. In AAAI, volume 4, pp. 709-715, 2004.
Rein Houthooft, Xi Chen, Yan Duan. John Schulman, Filip De Turck, and Pieter Abbeel. VIME:
Variational information maximizing exploration. NIPS, 2016.
Max Jaderberg. Wojciech M Czarnecki, lain Dunning, Luke Marris, Guy Lever, Antonio Garcia Castaneda, Charles Beattie, Neil C Rabinowitz, Ari S Moreos, Avraham Ruderman, al. Human- level performance first-person multiplayer games with population -aaeed deep reinforcement learning. arXiv:/8077 0/28/, 2018.

---

Under review as a conference paper at ICLR 2021
Vijay Krishna. Auction theory. Academic press, 2009.
Ryan Lowe, Abhinav Gupta, Jakob Foerster, Douwe Kiela, and Joelle Pineau. On the interaction between supervision and self-play in emergent communication. In ICLR, 2020.
Paul Milgrom et al. Auction theory. In Advances in economic theory: Fifth world congress, volume 1, pp. 32. Cambridge Univ. Press Cambridge, 1987.
Nolan Miller, Paul Resnick, and Richard Zeckhauser. Eliciting informative feedback: The peer- prediction method. Management Science, 51(9):135--177 2005.
Roger B Myerson. Mechanism design by an informed principal. Econometrica: Journal of the Econometric Society, pp. 1767-1797, 1983.
David V Pynadath and Milind Tambe. The communicative multiagent team decision problem:
Analyzing teamwork theories and models. Journal of artificial intelligence research, 16:389-423 2002.
Alec Radford, Luke Metz, and Soumith Chintala. Unsupervised representation learning with deep convolutional generative adversarial networks. ICLR, 2016.
Arthur I. Samuel. Some studies in machine learning using the game of checkers. recent progress. IBM Journal of Research and Development, 1 11(6):611667,, 1967.
Amartya Sen. Collective choice and social welfare. Harvard University Press, 1984.
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 without human knowledge. Nature, 550(7676):354339, 2017.
David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Mare Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, al. A general reinforcement learning algorithm that masters chess, shogi, and go through self-play, Science, 362(6419): 1140-1144 144, 2018.
Amanpreet Singh, Tushar Jain, and Sainbayar Sukhbaatar. Learning when to communicate at scale in multiagent cooperative and competitive tasks. In ICLR, 2019.
Sainbayar Sukhbaatar, Rob Fergus, et al. Learning multiagent communication with backpropagation. In NIPS, 2016.
R. S. Sutton and A. G Barto. Reinforcement learning: An introduction. A Bradford Book, 1998.
Gabriel Synnaeve, Nantas Nardelli, Alex Auvolat, Soumith Chintala, Timothée Lacroix, Zeming Lin, Florian Richoux, and Nicolas Usunier. Torchcraft: library for machine learning research on real-time strategy games. arXiv preprint 161 1.00225, 2016.
Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. ICLR, 2014.
Yichuan Tang. Towards learning multi-agent negotiations via self-play. 2019.
Gerald Tesauro. Temporal difference learning and td-gammon. Communications of the ACM, 38(3): 58-68, 1995.
William Vickrey. Counterspeculattin, auctions, and competitive sealed tenders. The Journal of Finance, 16(1):8-37, 1961.
Ronald J Williams.
Simple statistical gradient-following algorithms for connectionist reinforcement learning. Machine learning, 8(3-4):229-255 256, 1992.
10

---

Under review as a conference paper at ICLR 2021
A
THEORY
"...a human brain can learn such high-level abstractions if guided by the messages produced by other humans, which act as hints or indirect supervision for these high-level abstractions; and, language and the recombination and optimization of mental concepts provide an efficient evolutionary recombination operator, and this gives rise to rapid search the space of communicable ideas that help humans build up better high-level internal representations of their world." (Bengio, 2012)
A.1 GLOBAL OPTIMALLY
Proposition A.1. If is strongly truthful, (g) ((G) holds and R, is symmetric for any permutation of E [n]]] the value is given by,
j= sup wEW
nR1 daž (s dP.
(10)
Proof.
In this proof, we show that truthful game maximizes the designer's objective, then derive the closed form. To prove the former point, we show the following lemma.
Lemma A.1. The global optimum the designer's objective J J(; G) satisfies Pareto-optimally of joint objective,
Maximizewew U(w) and Minimizewew DKL (p go),
(11)
where,
U(w;R) Ego [V=0]= ff
v ( (z))
(12)
SES
and
VT* :- E,o [
(r E
(13)
AEAA
Proof. The first objective indicates the Bayesian Nash equilibrium w E W"( and the second indicates the belief state lo is as close to the true state as possible. From the assumption, R. is maximized if p is available for the each agent. Hence, from the theorem value iteration, there exists the solution (s) (s) for (s) for any s S. Hereinafter, we name x* and V* := V= the ideal policy and the ideal value, respectively.
From Eq (1), the ideal policy solves the designer's objective as J(w; 9) n.FEp(e)) [s)). Hence, the objective is find a policy n" (a|x, Φ) close where (T , o²) E W(G), that maximizes the first objective U (w). The policy x² can be broken down by the ideal policy x and wrong policy n' # x* as follows, t (a|x,, = -Eyo()))) [T (a|s)]
= (s (a|s)) + (1 (als
(14)
for the observations x X", where so S the state. Hence,
V=" (sul x) -p(x) (x0 + (1 - 9 (=(00 go(so) (sp) + Ep(x .0) [1 - [=( (=(s)) + (1 ( ('(ol)),
(15)
where,
V'(x0) = | R2 I do (s.1s)))))))))
(16)

---

Under review as a conference paper at ICLR 2021
and
('(a ()) == Ex(xls0) (x(()) (0((8)())
(17)
1 go (5
Thus, the error from the ideal value function can be written follows,
(50) V* (sol0) (1 (o())))( - ('(o)))).
(18)
The error is minimized if (50) as (s0) > (0 by the definition. From the Jensen's equation,
log Ep(eo) (80) 2 Ep(so) [log qo (su)]
DKL (p || qo) - H [p]
(19)
Therefore, the right-hand side determines the lower bound of the probability be maximized, Ep(so) (ao As the second term does not depend on o, the optimization is achieved by minimizing DKL. (p) |I (0).
Suppose that [((T, (((T,));)) -): J(G) > (G) for a non-truthful reporting policy such that ag (h(h) < From lemma A. (o h1,) for an internal state h; = f(x::) of Agent with an encoder f minimizes DEL (p || gg(s(h.)) (h.).. However, (s(2)) # (=(s),,), DKL (p (s(22)) > DKL (p (s(s)),)) holds. That contradicts the -areto-optimally. Therefore, dg must be truthful.
Next, since as (hilh) 1 holds from the assumption of strong truthfulness, from the symmetry of R. Eq (12) and (13) are written as follows.
j sup J sup pps) [nV]]]= = sup / (s) 0,6
8.6
0.0
n
sup 0.0
n (s) 2-1) II
dp(s)
j=2
sup
n (s) dp dp
0.0
sup 0.0
'RR, (s, a) do (als) (s(()(h) dpn dp.
(20)
Proposition A.2. If [C] is an unbiased truthful mechanism of G, self-play with GIC] converges to (g).
Proof.
Since [C] is unbiased, Ex,, [C.] 0 holds. Hence, for an arbitrary baseline b, b + C, also satisfies the
baseline condition. Therefore, from the policy gradient theorem (Sutton & Barto, 1998), self-play converges to J (G[C]). Further, since [C] is an unbiased truthful mechanism, J (G[C)) = - j([(C) = (() holds from Proposition A.I.D
general loss function b. Axx x -> Rxx for any strietly concave nonnegative function sb P(A) + Rxx is defined as follows:
4. = D
(21)
where d(azl-) is a point-wise probability that satisfies lim,-o Jnteaa,) dō(a, (ú,) for open ball ((e; āy), and Do is Bregman divergence (Bregman, 1967) defined by the following equation.
(oll) == (bp) - (b()) + / VV(l))(p--) q)
(22)
Sending truthful signal is the best response to minimize the expectation of the general loss function. For example, KL--diveregence is special case of Bregman divergence when 1a H [-]. and the following equation holds.
Exp [fal = f Du
dro(aylhs)
DKL (To(as)2;)
|I (o(a:)h)) O.
(23)
12

---

Under review as a conference paper at ICLR 2021
The equality holds if and only if 2, h4- Notice that (o(a))h;)) To(aylh;). Now, generalize the zero-one mechanism to arbitrary signaling games.
Proposition A.3. (Bregman mechanism) For any signaling games, if sup, / dV d < 1,
[IZa] is an unbiased truthful mechanism of g E B for a general cost function:
I (aaz)) == (a
(a(a2lz1) 0
Eo Lo(anlz1) Eo lolun (2)
n n
-1
(a(1l2)))
(24)
(v(ailzn) lu(02)zn)
where A = n.E - 11 is graph Laplacian.
Proof.
The problem we dealt with designing a scoring rule for information that satisfies two properties: 1) regularity, the score should be finite if the information is sufficiently correct, and 2) propernsss, the score should be maximized and only the information true. The well-known example of the scoring rule is mutual information (MI), which compares pair of probabilistic distributions p and in the logarithmic domain. However, MI cannot apply to continuous actions. Instead, we introduce a more general tool, the regular proper scoring rule as defined below.
Definition A.1. (Gneiting & Raftery, 2007) For set Q, F(-l-)) & (2: S - Bo is regular proper scoring rule iff there exists a strictly concave, real-valued function f on & (St) such that
F Fpllz) = f(D) - -J-- f (p(w),, x) dp(w) + (p.
(25)
for p B ( and x E Q where f* is subgradient of f that satisfies the following property.
f(a) f(p) / f (p,w) d(q - (w)
(26)
for E B (9).. We also define F for E Q (9) as F = Fa (pllz) dq(z), and describe a set of regular proper scoring rules B.
For F, F,F,,,22 B, the following property holds (Gneiting & Raftery, 2007).
1. Strict concavity: if q # then F(gll4) > F(pllg).
2. Filla) + aF2(pl))) + (()) E B where 0 and f are not dependent on
3. DD E B, where D& is the Bregman divergence.
Lemma A.2. For any F B and function E defined as shown below, ifsup, || (LVZ/d38. then [ is truthful mechanism of G.
(=(0)(z))= = { [F (To (
(i j) (i (i=j)
(27)
Proof. We prove that the surrogate objective of G|1l=], V = V 3l. is strictly concave, and VoV then 2; h4 with probability 1. We denote & as the truthful parameter where
a (3(h)1b4) The policy gradient for Φ is
B V. / (mo(a)(z))laa) dr dgo
V.V. dgp
V T dgs
V T dgs + 3 V oF (Ta(a (2:) (2) (e h()) dgs-
(28)
First, we consider the local optima, i.e. V.\= dg. 0 and Φ + G. For Gâteaux differential with respect $ ( T) / @1. VV 3Φ Vep 0 holds from the strict concaveity. At the
13

---

Under review as a conference paper at ICLR 2021
Table 3: Examples of the scoring rules, where k > 1, |ppl. = (1
p(a)) da)aaaddaa/) 'x. Readers can refer to
(Gneiting & Raftery, 2007) for examples of many other functions.
A
Z
x(p))
(a
Zero-one
Discrete
Discrete
P
T (a
Logarithmic
Discrete
Continuous
[p]
log (T(
Quadratic
Discrete
D/C
EecA p(a)
-1
2m²(a|2) - ( (-1=)
(Brier, 1950)
Continuous
DIC
11p13
2T<(a - (==)-1=)
Pseudospherical
Discrete
Continuous
( p(pa)*) 1/M
Ta(a|2)* -- (
(Good, 1952)
Continuous
Continuous
p 1-1
To ( --1 no mT(
VoVT global optima ie., V TT dqs = and Φ o. V.V = 3 V4. as sup, |l dV dé
holds. Next, if VV < 0,
B, the following equation holds for + á.
3 VV dgs = क VV== + 3 V)
dgp
dV
TV di + sup
Φ Vl dgø
dlf
VV dgo - in 3 VV
dgp
2 0.
(29)
Hence, VV 2 0 holds, and the equality holds if and only 3. Therefore, V is strictly concave, and the following equation holds for ag E o(1/k).
VOV3 (Øk) (Φx)) Oz = Φ. (a.8.) M
lim
(30)
Is is defined for both discrete and continuous actions. Table lists examples of scoring rules Es for arbitrary actions. particular, minimizing Ey. for continuous action is known as probability density estimation (Gneiting & Raftery, 2007).
-In a proper scoring rule (Gneiting & Raftery, 2007) since is a linear combination of Bregman
divergence. Hence, from Lemma A.2, [iIy] is truthful. Besides, since 1 I = 1 A 1 = 0, [iI,]
unbiased. D
Theorem A.1. (global optimally) For any games in Comm-POSG, TSP converges to the global optimum j if the following convergence condition are met,
Re V
sup
8,
(31)
Im V
where B < 5o is bounded mass parameter.
Proof.
From Proposition A.3, [IT,}] is unbiased truthful. Therefore, from Proposition A.2, convergence to the global optima is achieved. D
A.2 SELF-PLAY CONVERGES TO LOCAL OPTIMA
Theorem A.2. IfG 6 is non-truthful, self- self-play does not converge to the global optimum j(G).
Proof.
Example A.1. (One-bit two-way communication game) Fig. 4 shows an example of non-cooperative partially observable environment with 1-bit state. The reward structure is presented in Table The sum of rewards is maximized when both agents report the correct state to the environment,
Σ ( a) - 10 (otherwise)
[2c
(a== 02 =
1=1
Hence, the objective varies in the range 0 S J
2c.
14

---

Under review as a conference paper at ICLR 2021
12
31
01
012
21
22
Figure 3: Left: One-bit two-way communication game Peom- = A (0. 10 = {o).
and p(s) = 1/2. Agents given correct information from the environment with probability of > 0: Ps)(s) = X, P(ols) = - x. [1(5 2,) follows a Bernoulli distribution and estimates the state p(s) of the environment from observations and signals 2j
X. Let h;j I₁. Right: An example of the non-cooperative solutions: & = 1, (o, 1), z = (o, 0), a = (0, 1), (-1, and 2c.
r1 12
Table 4: Peom 's reward function R (² a). is constant that determines the nature of the game.
02
True
False
(21,
1
T
8
(c. C)
(1,-1)
a1
F
(0
Proposition A... Ifc < 1, (C < J (G holds.
Proof.
Since p(s) 1/2, we can assume = without loss of generality. Besides, we discuss only Agent because of symmetry. From Z {0, 1}. Agent I's messageling policy σΙ sends the correct information x or false information - z when it knows x. Hence, we can represent the policy by using parameter & E [0, 1] as follows.
(01(1 0)2-2
(x 1) (x = o)
(x(x|x)
(32)
1/2
Differentiating as with o gives the following.
dø
[22 [22-1
(x 1)
Geom (x= o)
(33)
dø 10
Therefore, from Eq (13), if (xt", E W" (C)m))
then the policy gradient for is follows.
d U( Φ) do / dq do dP dp
do
Vi
dq
dP
dp
dø
de
=x
1/2 (2z1 - 12 s=x1=1
=x / /(27) (221 - -1)R1 dır dz²z dq2 dzj dp
=A(1 - -2) / /(25) - 1) dr dm dgz dzj (221-1)
18
=X(1 - X) Σ (2z) 1) (Z1, (x1,
=1=0
s=1;=1
=X(1 - X) (1, R1 (1.0))
=X(1 -
(34)
15

---

Under review as a conference paper at ICLR 2021
As the policy gradient is negative from the assumption of с (0.1), Ø- gets the Nash equilibrium
from o 2 0, thereby resulting in always sending false information to the opposite:
[1-2 (==1)
o 0 (2|2)
(35)
11/2 (z=
Let (x1, = (x==)))22) 222) We can get J and J as follows.
J = / (21, dp²
(1, + J (1, o) 21(1 - A) ((o
2cA² +0+ 2c/22 (1 (1-1)²
2e x2 1
7 (1-))
2)2
(36)
and
j / ((11, dp²
1)A, + ((1, 2\(1 - 1) -2) ()( A)2
2cA² + 22(2 A) + +c//222222222 (1 1)2
2c 12 + 2X(1 A) + 1 -13
(37)
respectively. Therefore, J J 4cA(1 - A) > 0, and J < J holds. 0
From Proposition A.2, G Peom is the counterexample that global optimally does not occur.
A.3 ZERO-ONE MECHANISM SOLVES G
Proposition A.5. (zero-one mechanism) Let f Ax + {0,1) be a zero-one loss between an action and message ((a,l2y) = aj(1 2)) (1 a,)= and
I(alz) -1 | (((1122)
(a22)11) |
(38)
1 (1 c1 A)/2, then [iT] is an unbiased truthful mechanism of Poom and self-play with G. [7] converges to the global optima (( = 2c[1 - 3/4 (1 - -
Proof.
The following equation holds.
d
3, dg = dø / (Vi- - BIx dl d42) dd1
d
dØ
dø =- - 2)(1 c)) - 3// ʃ In dTž dæ dg2 dó
daz d'p dp
= =- - -)) c) -B1 / In d dge 1) dæg doz dP
==m==1
drž dup dzj A(1 - A)(1 c)) 3X² f(ee- 1)
(221-1)((azl2) 22
s=11=1==
X(1 - A)(1 - a) 3X2 Σ (22) - 1)((1(21)
=1=0
X(1 - X)(1 c) 3X? - E(110))
X(1 - -X)(1 c)) BA
=r- - (1 A
1
(39)
16

---

Under review as a conference paper at ICLR 2021
8
T1
12
22
True
False
Unohserved
(c,c)
(c+ B, ()
(c,c)
21
(c
3,c+ ())
(c,c)
(1,-1)
01
02
(c,
(-1,1)
(c/4,c/4)
21
11
2/
Figure 4: Left: The information released by one agent verified by another agent, and the infor- mation is incorrect, penalty is given. Right: State-action value function of ! Qr (24, .)).
Therefore, if B (1- (1 A)/A, then o3 holds, and J j holds. The value of J is clear from the proof of Lemma A.2.
[IZ] is also known as the peer prediction method (Miller al., 2005), which is inspired by peer review. This process is illustrated in Fig. 4 Left, and the state-action value functions are listed in Fig. Right.
B COMPLEXITY ANALYSIS
Although the computational complexity of AI., per iteration is O(n²) it involves the multiplication of n-order square matrices, we can reduce it to (nn²) to obtain Inp nLe L. 1. The spatial complexity is (n²?) and the sample size is (nn).
C EXPERIMENTAL ENVIRONMENTS
In the experiment, used two partial observation environments. This setting is the same as that adopted in existing studies (Sukhbaatar et al., 2016; Singh et al., 2019). Fig. shows the environments.
C.I PREDATOR PREY (PP)
Predator-Prey (PP) is widely used benchmark environment in MARL (Barrett et al., 201 Sukhbaatar et al., 2016; Singh et al., 2019). Multiple predators search for prey in a randomly initialized location in the grid world with a limited field of view. The field of view of a predator is limited so that only a few blocks can be seen. Therefore, for the predator to reach the prey faster, it necessary to inform other predators about the prey's location and the locations already searched. Thus, the prey's 's location is conveyed through communication among the predators, but predators also send false messages to keep other predators away from the prey.
In this experiment, experiments are performed using PP-3 and PP-5, which have two difficulty levels. In PP-3, the range of the visual field is set to 0 5 5 environment. In PP-5, the field of view is set to 1 in 10 x 10 environment. The numbers represent the number of agents.
C.2 TRAFFIC JUNCTION (TJ)
Traffic Junction (TJ) is simplified road intersection task. An body agent with limited field of view informs the other bodies of its location to avoid collisions. In this experiment, the difficulty level of TJ is changed to three. TJ-5 solves the task of crossing two direct one streets. For TJ-10, there are two lanes, and each body can not only go straight, but also turn left or right. For TJ-20, the two-lane road will comprise two parallel roads, for total of four intersections, Each number corresponds to n.
In the initial state, each vehicle is given starting point and destination and is trained follow determined path as fast as possible while avoiding collisions. The agent is in each body and takes two actions, i.e., accelerator and brake, in single time step. It is crucial ensure that other vehicles do
17

---

Under review as a conference paper at ICLR 2021
not approach each other to prevent collision while making good of multiagent communication. That is similar to blinkers and brake lights.
C.3 STARCRAFT: BLOOD WARS (SC)
Explore: In order complete the exploration task, the agent must be within specific range (field of view) of the enemy unit. Once the agent is within the enemy unit's field of view, it does not take any further action. The reward structure of the enemy unit the same as the PP task, with the only difference being that the agent The point is that instead of being in the same place, you explore the enemy unit's range of vision and get a non-negative reward. Medic units that do not attack enemy units are used to prevent combat from interfering with the mission objective. For observation, for each agent, it is the agent's (absolute x, absolute y) and the enemy's 's (relative x, relative y. visible), where visiblea is visual range. If the enemy is not in exploration range, the relative and relative y are zero. The agent has nine actions to choose from: eight basic directions and one stay action.
Agents make their own observations (absolute x, absolute health point shield, weapon cooldown, previous action) and (relative x, relative y. visible, health point + shield, weapon cooldown). Relative x and y are only observed when the enemy is visible, corresponds to visible flag. All observations are normalized to lie between (0, 1). The agent must choose from 9+M actions, including 9 basic actions and I action to attack M agents. The attack action is only effective if the enemy within the agent's view, otherwise is a no-problem. In combat, the environment doesn't 't compare to Starcraft's predecessors. The setup is much more difficult, restrictive, new and different, and therefore not directly comparable.
Combat:
In Combat task, we give a negative reward Ptime -..01 at each time step to avoid delaying the enemy team's detection. When an agent is not participating in battle, at each time step, the agent is rewarded with (i) normalized health status the current and previous time step, and (ii) normalized health status at the previous time step displays the time steps of the enemies you have attacked so far and the current time step. The final reward for each agent consists (i) all remaining health 3 as a negative reward and (ii) 5 health #3 to all living enemies as a negative reward when you lose. In this task, a group of enemies is randomly initialized in half of the map. Thus the other half making communication-demandiie even more difficult.
all remaining health 3 as positive reward if the agent wins. Give
tasks
D HYPERPARAMETERS
Table 5: Hyperparameters used in the experiment, / are grid searched in space {0.1, 1, 10, 100J, and the best parameter is shown. The other parameters are not adjusted.
Notation
Value
Agents
n
(3,5, 5, 10, 20)
Observation Internal state
Iti X has E H
R
R
Message
Zti E Z
6
Actions
as A
{+, 1, L. astop)
True state
St E S
{0, 10.1]220 10.1
Episode length
T
20
Learning rate
0.001
Truthful rate
,9
Discount rate
2
1.0
Metrics
-H
18


Reviews:
[{"review_id": "v1WChO-RBc", "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": "**Summary:**\n\nThis work presents an auxiliary loss that promotes truthfulness in non-cooperative multi-agent games with communication channels. The truthfulness is promoted through prediction rewards, which capture how well each agent can model other agents' policies via observing their messages. For this mechanism to work, it assumes that each agent has access to other policies, and such an assumption can be satisfied under the self-play / centralized-learning decentralized-execution / shared-weights setup. Having such access to the policy weights, an agent can observe how consistent was their action with their broadcasted message which is a function over their hidden state. Thus by promoting consistency between their actions and messages, truthfulness is achieved. This paper provides theoretical justification of the proposed mechanism and introduces ideas from mechanism design literature in multi-agent reinforcement learning under a non-cooperative setup (not sharing rewards).\n\nPros: \n- Introducing truthful mechanism design and providing theoretical guarantees in non-cooperative MARL is an interesting idea. The part that I find significant contribution is more on the theoretical justification than the mechanism itself (see related work section comments).\n\nCons: \n- Motivation is not that clear to me and the introduction / related work doesn't cover relevant work as it should.\n- Notation different from what is common in MARL and makes it difficult to read at parts\n\n**0 - Abstract**\n\n\"Evolutionary frameworks such as self-play converge to bad local optima in case of multi-agent reinforcement learning in non-cooperative partially observable environments with communication due to information asymmetry.\" - I think this needs further discussion on the main text. how information asymmetry causes bad local optima? Also, as I mention later, this work is similar to centralized-learning/decentralized-execution work and as such, it should be presented in the abstract as well.\n\nAlso as I mention later, mechanism design in MARL is not new and intrinsic rewards have been applied before to promote cooperation in mixed incentives games (e.g. [1]).\n\nImaginary rewards are mentioned in the abstract however this is not a common term I believe. The more common term is the intrinsic or auxiliary reward.\n\n**1 - Introduction**\n\n\"improved exploration coverage\" - the main idea in these papers was not related to exploration coverage but to information passing policies. why exploration is mentioned here?\n\n\"improper bias is injected into the state representation\" - What is improper bias? I would feel safer with this term if it was referenced or given a concrete example of what that means.\n\n\"... also the robots (Jaderberg et al., 2018), \" - this citation refers to multiplayer first-person games, not robots.\n\n\" ..actions such as concealing information and deceiving other agents at equilibrium.. \" - cite [https://arxiv.org/pdf/1803.03453.pdf](https://arxiv.org/pdf/1803.03453.pdf) as well as Singh et al. is citing this for the quote.\n\n**2 - Related Work**\n\nMissing literature on centralized learning / decentralized execution (CLDE) which is related to the current work in the sense that self-play with weight sharing is the same as CLDE [3]\n\nWorld models seem irrelevant as they are discussed with respect to their exploratory power or as applications of RNNs - why exploration is part of the discussion here? (generally, the application of RNNs is not a concept that worths emphasizing I believe but that's just an opinion - most of the multi-agent communication algorithms are usually using RNNs to equip the agents with some memory and compensate for the potential violation of the markovian assumption of the MDP)\n\nCommunication in mixed cooperative-competitive environments but also Sequential Social Dilemmas seems relevant as well and not discussed. For example [1, 2, 3]. In fact, in [1] the authors are using intrinsic rewards which can be thought of as mechanism design promoting cooperation.\n\nAlso, the use of intrinsic and auxiliary rewards in multi-agent communication seems relevant to mechanism design but not discussed as well. e.g.[6]\n\n\"To the best of our knowledge, introducing mechanism design to MARL is a new direction for\nthe deep-learning community.\" - What is the difference between this and intrinsic rewards which are currently under active research? e.g. [1]\n\n**3.1 - COMM-POSG**\n\nIs the state transition probability $\\in S \\times A \\times S$ or $S \\times A^n \\times S$?\n\n\"We denote the social welfare at the BNE is *J , and the global maximum ˆJ. In general, *J != ˆJ holds, which is closely related to the information asymmetry.\" - is there a reference for this or can you provide an explanation?\n\n**3.3 - Truthfulness**\n\n\"eventually it also maximizes *J will be maximized\" - can you clarify/fix this sentence?\n\n**4.1 - Imaginary Reward**\n\n\"However, the baseline function is a quantity that is determined based on the value function of a single agent, whereas the imaginary reward is different in that (1) it affects the value function of each agent\" - This has been addressed before in [4] where a baseline is designed to compute a separate value per agent. \n\nAlthough I like the idea of imaginary rewards I don't understand what is the difference between this and auxiliary rewards or intrinsic/extrinsic breakdown which is a common technique in MARL. Why not mix directly on the reals and represent it as a complex number? Eventually, you mix them in Alg 1. (5) so if there isn't any other theoretical justification, why introduce a new notation/term? My point is that it makes reading this harder than it should because it's not common (if you have examples of work using a similar definition please let me know).\n\n**5 - Numerical Experiment**\n\nCan you present the results also in terms of Avg. number of steps (for pred prey) and success % (for junction), similarly to [7]? The way it is I can't verify that the numbers you are reporting are comparable to existing runs of the compared work (if you can reproduce the same number, if not I'd be ok with some justification as to why the numbers differ or why used different reporting metric). Similarly for StarCraft, what is the win ratio and average steps?\n\n**6 - Concluding Remark**\n\n\"To the best of our knowledge, introducing mechanism design to MARL is a new direction for the deep-learning community\" - As mentioned, intrinsic and auxiliary rewards can be thought of as mechanism design, and as such mechanism design to MARL is not as novel.\n\n[update] reduced score given the lack of \n\n[1] Jaques, Natasha, et al. \"Social influence as intrinsic motivation for multi-agent deep reinforcement learning.\" International Conference on Machine Learning. PMLR, 2019.\n\n[2] Leibo, Joel Z., et al. \"Multi-agent reinforcement learning in sequential social dilemmas.\" arXiv preprint arXiv:1702.03037 (2017).\n\n[3] Lowe, Ryan, et al. \"Multi-agent actor-critic for mixed cooperative-competitive environments.\" Advances in neural information processing systems. 2017.\n\n[4] Foerster, Jakob, et al. \"Counterfactual multi-agent policy gradients.\" arXiv preprint arXiv:1705.08926 (2017).\n\n[5] Mordatch, Igor, and Pieter Abbeel. \"Emergence of grounded compositional language in multi-agent populations.\" arXiv preprint arXiv:1703.04908 (2017).\n\n[6] Singh, Satinder, et al. \"Intrinsically motivated reinforcement learning: An evolutionary perspective.\" IEEE Transactions on Autonomous Mental Development 2.2 (2010): 70-82.\n\n[7] Singh, Amanpreet, Tushar Jain, and Sainbayar Sukhbaatar. \"Learning when to communicate at scale in multiagent cooperative and competitive tasks.\" arXiv preprint arXiv:1812.09755 (2018).", "extra_scores": {}, "extra_text": {}}, {"review_id": "Vbk0ixUBmBg", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 4, "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 examines the setting of partially observable stochastic games where agents have the possibility of communication.  The approach taken is what would be termed “direct revelation” in mechanism design: agents are supposed to reveal their full internal state / history to each other at each step.  This gives the most complete information possible to enable good decisions.  However, agents may not have an incentive to report truthfully, so an approach based on peer prediction is used to incentivize this.  The results show improvements over prior approaches to communication in three tasks: predator prey, traffic junction, and StarCraft.\n\nI like the motivation behind this paper, and agree that the idea of reasoning about the incentives to communicate and using techniques like peer prediction to encourage this is an interesting and important approach.  However, I have some conceptual issues with exact way the techniques are used and some presentation issues make parts of the approach unclear.\n\nDetailed comments:\n\n1) The paper cites quite a bit of work from the economics, statistics, and game theory communities, some of which is relevant (e.g. scoring rules and peer prediction) but quite a bit of which is not (broad mechanism design papers, VCG).\n\n2) The paper is quite clear about the objective of the system designer, optimizing social welfare per equation (1) but never defines, except perhaps implicitly in Algorithm 1, what the objective of each agent is.  This manifests in a number of ways (see also points 3, 7, and 8), but one immediate issue is that I’m not sure I agree with the claim at the end of 4.1 that J^* != J is related to information asymmetry.  It is possible this is an exacerbating factor, but I would expect problems even in a complete information setting due to agents having different incentives.\n\n3) I don’t see why Proposition 3.1 (and therefore the results that rely on it such as Prop 4.1 and Theorem 4.1) should be true in general.  It makes sense in cooperative settings, such as the predator prey one used in the experiments, where each agent on a team gets the same reward.  But in more general settings, like traffic junction, agents may not have the same incentives.  So even if they all truthfully reveal their information we shouldn’t expect their individual decisions to cause us to reach the global optimum.  There is a large literature on the “Price of Anarchy” which looks at bounding the size of this gap, but apart from very special cases there is almost always a gap.  I tried looking at the proof but couldn’t get any clarity about this.\n\n4) The “Imaginary Rewards” are typically called payments or transfers.  Mechanisms which ensure they add to zero are referred to as “budget balanced” or sometimes “redistribution” mechanisms.  This actually requires quite a bit of care to establish incentive properties because in naïve implementation, which the subtracting the mean one used in this paper appears to be, there can actually be incentive issues introduced by this redistribution process.\n\n5) The notation for a scoring rule F(p_s || s) is a very special case (sometimes called “local”) that really only the log score satisfies.  In general it should be F(p||s) as the score depends on the whole distribution, not just p_s.  See, e.g., the Brier score.\n\n6) I found equation (6) quite hard to parse because the relevant notation is scattered.  If I understand it correctly, the idea is that In particular, z_{tji}  is signal of a single agent j, which we should expect to be it’s pre-state.  Each agent collects the messages of all the other agents and computes its post state (which I’m not sure why is denoted as a sample from q).  \\pi takes a post state as an argument, but can equally well be applied to the pre state reported by another agent to predict the agent’s action, which is why we can apply a scoring rule.  But given all this I’m not clear why the score in (6) is computed based on the a_{ti} sampled.  We have both policy distributions so instead could compute the expected score which would be lower variance.\n\n7) Similar to point 3, I don’t see why we should expect Theorem 4.1 to hold in general.  Even if an agent maximizes its imaginary reward by truthfully reporting, it may be worthwhile to lie and accept a lower imaginary reward in exchange for a larger actual reward.  I don’t see anything ruling this out.   This result makes sense in the cooperative setting, but there I don’t see why and agent would have an incentive to lie in the first place so this whole piece seems redundant.\n\n8) In the experiments, there is improvement in both cooperative and non-cooperative settings from SP IC3Net to TSP IC3Net.  I think this needs to be investigated and discussed further.  In particular, as discussed in point 7, in games like predator prey there doesn’t seem to be any incentive to misreport so that whole piece of TSP shouldn’t be doing much.  But clearly something quite different is happening.  Perhaps the TSP version uses the channel in a fundamentally different way?  E.g. is something (and there aren’t enough details for me to understand how this works so I’m not exactly sure what) enforcing a direct revelation structure (even without truthfulness) is a way the SP version does not?  This seems like a separate part of the contribution and important to disentangle from the incentive part.  Perhaps there is a natural way to do an ablation for this?\n\n9) The paper, and particularly the introduction, has a number of grammatical and style issues.  It needs a careful copyediting pass.\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "6w60rOTu81", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "1. Summary and contributions:\nThe author claimed that evolutionary learning, such as self-play converge to local optima in multi-agent partially observed non-cooperative settings. They proposed a truthful self-play method and add imaginary rewards into self-play method by using the idea of reverse game theory. They evaluated their method on three different settings.\nI have read this paper for several times, however because of the poor writing, it's very hard to follow the key idea of this paper. \nAlso, I have some author concerns about the technique and experiment. \nI will list some of the issues as follows.\n\n2. Concerns:\n(1) I wonder the author talk about some key self-play methods, such as David's Generalised weakened fictitious play[1], Johannes's Fictitious Self-Play[2]  in partially observed MDPs, i.e., imperfect information game in the game theory community. Typically, these methods have good convergence on partially observed non-cooperative games.\nIf the authors can compare the Johannes's method on the experiment, it will be better.\n(2) The written skill about this paper needs to improve. Some paragraphs need to be reorganized. For example, in section 2, the author talks about the related work on self-play on the second paragraph. It's confusing of say \"RNNs such as world models are capable of more comprehensive ranges of exploration in partially observable environments ...\". Typically, self-play is a kind of methods in game theory while RNN is a kind of deep learning neural networks. After that, the author talk about evolutionary learning and supervised learning. \nother example, such as \"To the best of our knowledge, there are no studies that have introduced truthful mechanisms into the field of MARL, but it may be possible to introduce it by using agents that can learn flexibly, such as neural networks.\"\n(3) The experiment results are not very clear. For example, the x-axis and y-axis in Figure 2 are not defined, so that it's hard to confirm the conclusion.\n\n3. Questions:\n(1) What's global maximum $\\hat{J}$ ? Giving an example and explaining why $J^{*} \\neq \\hat{J}$ will be better.\n(2) What's post-state? I only find the definition of pre-state in section 3.1.\n(3) it's not clear about section 3.2. I's a little difficult to make the connection between section 3.1 and 3.2. Adding some figures will be better.\n\n4. some issues/typos:\n(1) page 1, pertially observable stochastic games (POSG): pertially -> partially?\n(2) Comm-POSG is used in page 2, however it's defined in page 3.\n(3) page 2: \"interacts each other\" -> \"interacts with each other\"\n(4) remove \", and\" in Defintion 3.1 after \"an observation probability\"\n(5) page 3: $r_{ti}$ is reward, $\\pi_{i}$ is a stochastic policy.\n(6) page 4: all the agent share -> all the agents share\n(7) To remain the social welfare of the system is real\n\n[1] Leslie, David S., and Edmund J. Collins. \"Generalised weakened fictitious play.\" Games and Economic Behavior 56, no. 2 (2006): 285-298.\n[2] Heinrich, Johannes, Marc Lanctot, and David Silver. \"Fictitious self-play in extensive-form games.\" In International Conference on Machine Learning, pp. 805-813. 2015.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "4ySteA2O0m", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "## Summary\n\nThe paper proposes an elegant baseline addition to policy gradient / self play to encourage truthful signaling in Comm-POSGs. It outperforms self-play on various communication domains and uses a number of interesting concepts. Cool paper - I think ICLR will enjoy reading!\n\n## Score\n\nClear accept - pending a more thorough check of the appendices.\n\n=== Edit ===\n\nOther more confident reviewers have pointed out some concerns. I am still positive about the paper, but due to lack of rebuttal I am going to downgrade from my initial score.\n\n## Positives\n\nThe addition is elegant and the imaginary component does not leak into the networks.\n\nDoes not add a bias to the PG objective.\n\nUtilizing an imaginary reward is a very interesting approach - maybe there are domains that this is useful?\n\nClearly good results on the domains tested.\n\n## Concerns\n\nHow is beta chosen in the experiments?\n\nLimited alternative baselines. Is there another algorithm that will perform well here?\n\n## Other Things\n\nPage 1: “P*e*rtially observable…”\n\nPage 2: I prefer “identity matrix” over “unit matrix”\n\nPage 3: “...but interacts each other” - ?\n\nPage 4: “weight” is not defined yet (maybe call parameters?) - clarify if theta and phi are scalars or vectors. Wording implies they are scalars.\n\nPage 4: CRA could do with a small diagram showing the interactions\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper exposes a modification of self-play (in a non-cooperative setup) where agents expose their internal states to each other, and adds a "truthfulness" mechanism to ensure the agents do not hide information to each other.

The reviewers generally agree that the ideas presented, in particular the imaginary rewards, is interesting and should be explored further. The experimental results are good.

However, reviewers point out many problems related to clarity, writing and notations, and they note many typos. The motivation of this work also needs to be explained further.
Reviewers also find that the related work section needs to be remade, as it both lacks citations, and cites works that are not really relevant. This work positioning with respect to these previous works also needs to be expanded.
The reviewers also point out that the experimental results should be discussed further.

Generally, the paper cannot be published in its current state, and unfortunately the authors have not submitted an updated version or answers to the reviews. I therefore recommend rejection for this paper.
Decision: Reject