Year: 2020

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 selfplay 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.

heading: 1 INTRODUCTION
text: 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 AlphaGo (Silver et al., 2017), but also improved exploration coverage in partially observable environments and communication (Sukhbaatar et al., 2016; Singh et al., 2019) to exchange their internal representations, such as explored observation and hidden state in RNNs. Evolutionary learning is expected to 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 noncooperative 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 of the environment, and thus, it does not have sufficient knowledge to 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 et 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-play to non-cooperative partially observable environments via mechanism design (Myerson, 1983; Miller et al., 2005), which is 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, a mechanism for evaluating the validity of information exchanged between agents in a decentralized environment, which is calculated based on social influence on the signals. We formulate the non-cooperative partially observable environment as an extention of the pertially observable stochastic games (POSG) (Hansen et 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
method (Miller et al., 2005) and apply it to self-play. 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, input, 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 et 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-ofthe-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 is 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 JnK := {1, . . . , n}. R is a set of real numbers. i is the imaginary unit. Reu and Imu are 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−i is a (n− 1)-tuple obtained by removing the i-th entry from a. Let 1 := (1, . . . , 1)T. Matrices are shown in uppercase letters L := (`ij). E is the unit matrix. The set of probability distributions based on the support X is described as P(X ).

heading: 2 RELATED WORK
text: 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 AI community in the latter half of the century. Samuel (Samuel, 1967) introduced self-play as a framework for sharing a 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(λ) (Sutton & Barto, 1998) and achieve professionalgrade 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 eliminating the bias of human knowledge in supervision is the advantage of self-play.
Self-play is 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 et al., 2019). Bansal et 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 evolutionary 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-POMDP-Com (Goldman & Zilberstein, 2003) and COMMTDP (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
Comm-POSG as a superset of POSGs (Hansen et al., 2004), a more general class of multi-agent games including the cases of non-cooperativity (Hansen et al., 2004).
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. A typical truthful mechanism is the VCG mechanism (Vickrey, 1961), which is a 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 a value function if interpreted from a 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 a peer prediction method (Miller et al., 2005) that guarantees truthfulness with respect to reporting beliefs about arbitrary probability distributions using proper scoring rules (Gneiting & Raftery, 2007).

heading: 3 PROBLEM DEFINITION

heading: 3.1 COMM-POSG
text: A communicative partially-observable stochastic game (Comm-POSG) is a class of non-cooperative Bayesian games in which every agent does not 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.
Definition 3.1 (Hansen et al., 2004) POSG 〈n, T,S,A,X , T ,P,R〉 is a class for multi-agent decision making under uncertainty in which the state evolves over time 1 ≤ t ≤ T , where
• n is the number of agents, • T is a horizon i.e., the episode length, • S is a set of discrete/continuous state st ∈ S with an initial probabilistic distribution p(s0), • A is a set of discrete/continuous action ati ∈ A, • X is a set of discrete/continuous observation xti ∈ X , • T ∈ P (S ×A× S) is state transition probability, • P ∈ P (S × Xn) is an observation probability, and • R : S ×An → Rn is a reward function that outputs an n-dimensional vector.
In Comm-POSGs, every agent further follows a message protocol Zn×n, where Z is the discrete/continuous signal space. The complete information exchanged among the agent in time is Zt, where Zt := (ztij)i,j∈JnK ∈ Zn×n is a signal matrix in which (i, j)-th entry ztij represents a signal from Agent i to Agent j at t. The i-th diagonal entry of Zt, hti := ztii represents the pre-state, an internal state of i-th agent before receiving the singals from the others. A game in Comm-POSG is denoted as G := 〈n, T,S,A,X , T ,P,R,Z〉. The objective function of Comm-POSG is social welfare (Arrow, 1963) defined by the following,
J := n∑ i=1 V πi ; V πi := Eπi [ T∑ t=1 γt−1rti ] , (1)
where γ ∈ [0, 1] is discount rate, rti is reward πi is a stochastic policy, and V πi is the value function. In extensive-form games including Comm-POSG, in addition to the information in the environment, the information of other agents cannot be observed. In the optimization problem under these assumptions, a policy converges to 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̂ . In general, J∗ 6= Ĵ holds, which is closely related to the information asymmetry.

heading: 3.2 COMMUNICATIVE RECURRENT AGENTS
text: In order to propose an optimization algorithm in this paper, we do not propose a concrete structure of the network, but we propose an abstract structure that can cover existing neural communication models (Sukhbaatar et al., 2016; Singh et al., 2019), namely communicative recurrent agents (CRAs) 〈fφ, σφ, qφ, πθ〉, where
• fφ(ĥt−1,i, xti) 7→ Z is a deep RNN for the high-dimensional input xti ∈ X and the previous post-state ĥt−1,i ∈ Z , with a parameter φ and an initial state ĥ0 ∈ Z ,
• σφ(zti|hti) is a stochastic messaging policy for a pre-state hti := fφ(ĥt−1,i, xti), • qφ(ĥti|ẑti) is a stochastic model for a post-state ĥti ∈ Z and the received messages ẑti := Z T t:i = (zt1i, . . . , zt,i−1,i, hti, zt,i+1,i, . . . , ztni) T, and
• πθ(ati|ĥti) 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 are updated based on the cumulative reward after the episode.
In addition to the recurrent agent’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 hti in the hidden layer of the RNN and the received signals ẑti,−i from other agents. Hence, the veracity of the signals zti is the point of contention.

heading: 3.3 TRUTHFULNESS
text: In mechanism design, a truthful game (Vickrey, 1961) is a game in which all agents make an honest reporting in the Bayesian Nash equilibrium. In Comm-POSGs, the truthfulness of the game is achieved if all the sent signal equals the pre-state ztij = hti i.e., all the agent share a complete information. In such case, all the agents can have the same information ẑti = ht := (ht1, . . . , htn)T 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.
Dφ(Zt) := 1
n n∑ i=1 H [ qφ(ĥt|ẑti) ] + 1 n2 n∑ i=1 n∑ j=1 DKL ( qφ(ĥt|ẑti) || qφ(ĥt|ẑtj) ) . (2)
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, H [p(st)]; since achieving truthfulness is essentially the same problem as minimizing Dφ, eventually it also maximizes J∗ will be maximized. Proposition 3.1. (global optimally) For any games G in Comm-POSG, if Dφ(Zt) = H [p(st)] for 0 ≤ t ≤ T andRi is symmetric for any permutation of i ∈ JnK, J∗(G) = Ĵ(G) holds1.

heading: 4 PROPOSED FRAMEWORK
text: An obvious way to achieve truthful learning is to add Dφ as a 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 ĥti, so the exact amount cannot be measured by the designer of the learner. If post-states are 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, a general framework for unbiased regularization in Comm-POSG, and the other is the introduction of peer prediction method (Miller et al., 2005), a truthful mechanism to encourage honest reporting based solely on observable variables. In the following, each of 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.

heading: 4.1 IMAGINARY REWARD
text: 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
1Refer Section A for the proofs.
Algorithm 1 The truthful self-play (TSP). Require: Comm-POSG 〈n, T,S,A,X , T ,P,R,Z〉, CRA 〈fφ, σφ, qφ, πθ〉 with initial weight w0 = 〈θ0, φ0〉 and initial state ĥ0, learning rate α > 0, and mass parameter β ≥ 0. Initialize w← w0. for each episode do
Genesis: s1 ∼ p(s), ĥ0i ← ĥ0, ∀i ∈ JnK. for t = 1 to T do
1. Self-Play Observe xt ∼ P(·|st). Update pre-state hti ← fφ(ĥt−1,i, xti), ∀i ∈ JnK. Generate message zti ∼ σφ(·|hti), ∀i ∈ JnK. Send message Zt ← (zt1, . . . , ztn). Receive the message ẑti ← ZTt:i, ∀i ∈ JnK. Update post-state ĥti ∼ qφ(·|ẑti), ∀i ∈ JnK. Act ati ∼ πθ(·|ĥti), ∀i ∈ JnK. Get the real reward rt ← R(st,at). 2. Compute a score matrix Lt with the peer prediction mechanism,
`tij ← {
log πθ(ati|ztji) (i 6= j) 0 (i = j) , ∀i, j ∈ JnK. (3)
3. Combine the real and imaginary rewards,
R+t ← Rt + i∆Lt . (4)
4. Update the weights by policy gradient (Williams, 1992),
gt ← n∑ i=1  n∑ j=1 r+tji  ∇w [log πθ(ati|ĥti) + log qφ(ĥti|ẑti) + log σφ(zti|ĥt−1,i, xti)] , w← w + αRegt + αβImgt. (5)
5. Proceed to the next state st+1 ∼ T (·|st,at). end for
end for return w
environments, including Comm-POSG, are of no other entities than agent and environment, twodimensional 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 are ordered by the mass parameter β during training, which allows the weights of the network to maintain a real structure.
The whole imaginary reward is denoted2 as iY = (iyij)i,j∈JnK where iyij is the imaginary reward passed from Agent i to Agent j, and the complex reward for the whole game is R+ := R + iY where R is a diagonal matrix with the environmental reward ri as (i, i)-th entry. We write G[iY] 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[iY] is truthful and R+ is an Hermitian matrix, J∗(G[iY]) = Ĵ(G) holds.
Proof. Since G[iY] is truthful, J∗(G[iY]) = Ĵ(G[iY]) holds from Proposition 3.1. Further, since R+ is Hermitian, iyij = −iyji, and hence Im Ĵ(G[iY]) = 0 holds; Ĵ(G[iY]) = Ĵ(G) holds.
2Note the use of i for imaginary units and i for indices.
This indicates that J∗(G[iY]) ≥ J∗(G), indicating that the BNE could be improved by introducing imaginary rewards. Also, since ∑n i=1 ∑n j=1 iyij = 0 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 baseline 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 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 and (2) it is a meaningful quantity only when n ≥ 2 and is not observed when n = 1.

heading: 4.2 PEER PREDICTION MECHANISM
text: 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 a 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(ps‖s) where ps is the probability of occurrence reported by the verifier for the event s, and F(ps‖s) is the score to be obtained if the reported event s actually occurred. The scoring rule is proper if an honest declaration consistent with the beliefs of the verifier and the reported ps 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 is strictly proper is the logarithmic scoring rule F(ps‖s) = log ps, where the expected value for a 1-bit signal is the cross-entropy p∗s log ps + (1− p∗s) log(1− ps) for belief p∗s . One can find that ps = p∗s is 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 a 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 it. The peer prediction mechanism (Miller et al., 2005) is denoted as F(p(s|z)‖s) under the assumption that (1) the type of event s and the signal z 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 ati ∼ πθ|st for the true state st ∈ S. In self-play, the conditions of 1 and 2 can be satisfied because the prior πθ is shared among the agents, and furthermore, the post-state in Comm-POSG corresponds to 3, 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 Lt as follows,
Lt := (`(ati|ztji))i,j∈JnK; `(ati|ztji) := F(πθ(ati|ztji)‖ati) = log πθ(ati|ztji), (6)
which is an n-order square matrix representing the score from Agent i to Agent j.

heading: 4.3 THE TRUTHFUL SELF-PLAY
text: In our framework, a truthful mechanism is constructed by introducing the proper prediction mechanism into imaginary rewards. Since the score matrix Lt 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 ∆ := E − 11T/n.
Yt = ∆Lt = 1
n
 n− 1 −1 . . . −1 −1 n− 1 . . . −1
... ...
. . . ...
−1 −1 . . . n− 1
  0 `(at2|zt12) . . . `(atn|zt1n) `(at1|zt21) 0 . . . `(atn|zt2n)
... ...
. . . ...
`(at1|ztn1) `(at2|ztn2) . . . 0
 , (7)
to get
R+t = Rt + i∆Lt, (8)
which is the formula that connects reinforcement learning and mechanism design.
Theorem 4.1. (global optimally) For any games in Comm-POSG, TSP converges to the global optimum Ĵ if the following convergence condition are met,
sup φ ∣∣∣∣∂ ReV πθ∂ ImV πθ ∣∣∣∣ < β, (9)
where β <∞ is bounded mass parameter.
Proof (in summary.) R + i∆L is Hermitian; and if Eq (9) holds, then G[i∆L] is truthful from Proposition A.3. Therefore, from Proposition 4.1, convergence to the global optima is achieved.

heading: 5 NUMERICAL EXPERIMENT
text: 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) in which predators with limited vision look for a prey on a square grid. (b) a 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.
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 to 20 agents. The hyperparameters are listed in the appendix. With regard CRAs, three models namely LSTM, CommNet (Sukhbaatar et 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 a 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 SP for all tasks. Fig. 2 (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 state-of-the-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 on a 50×50-cell grid; similar to PP, the reward is a competitive task where the reward is divided by the number of medics found. (ii) In the combat task, 10 Marines versus 3 Zealots fight on a 50×50 cell grid. The maximum step of the

heading: StarCraft task CommNet IC3Net IC3Net w/ TSP
text: 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.

heading: 6 CONCLUDING REMARK
text: Our objective was to construct a general framework for emergent unbiased state representation without any supervision. Firstly, we proposed the TSP and theoretically clarified its convergence to the global optimum in the general case. Secondly, we performed experiments involving up to 20 agents and achieved the state-of-the-art performance for all the tasks. Herein, we summarize the advantages of our framework.
1. Strong convergence: TSP guarantees convergence to the global optimum theoretically and experimentally; self-play cannot provide such a guarantee. Besides, the imaginary reward i∆L satisfies the baseline condition.
2. Simple solution: The only modification required for TSP is that i∆L should be added to the baseline in order to easily implement it for deep learning software libraries such as TensorFlow and PyTorch.
3. Broad coverage: TSP is a general framework, the same as self-play. Since TSP is independent of both agents and environments and supports both discrete and continuous control, it can be applied to a wide range of domains. No supervision is required.
To the best of our knowledge, introducing mechanism design to MARL is a new direction for the deep-learning community. In future work, we will consider fairness (Sen, 1984) as the social choice function. We expect that many other frameworks will be developed by using the methodology employed in this study.

heading: A THEORY
text: “. . . 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 in the space of communicable ideas that help humans build up better high-level internal representations of their world.” (Bengio, 2012)

heading: A.1 GLOBAL OPTIMALLY
text: Proposition A.1. If G ∈ G is strongly truthful, J∗(G) = Ĵ(G) holds and Ri is symmetric for any permutation of i ∈ JnK, the value is given by,
Ĵ = sup w∈W
∫ nR1 dπnθ dqnφ(s|h) dP. (10)

heading: Proof.
text: In this proof, we show that a 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 of the designer’s objective J(w;G) satisfies Pareto-optimally of a joint objective,
Maximizew∈W U(w) and Minimizew∈W DKL (p || qφ) , (11) where,
U(w;R) := Eqφ [V πθ ] = ∫ s∈S,ẑ∈Zn V πθ (s) dqφ(s|hi, z−i) dσφ(ẑ), (12)
and
V πθ (s) := Eπθ [Ri|s] = ∫ a∈An Ri(s,a) dπnθ (a|s), ∀s ∈ S. (13)
Proof. The first objective indicates the Bayesian Nash equilibrium w ∈ W∗(G), and the second indicates the belief state qφ is as close to the true state p as possible. From the assumption, R is maximized if p is available for the each agent. Hence, from the theorem of value iteration, there exists the solution π?(s) for V (s) for any s ∈ S . Hereinafter, we name π? 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;G) = nEp(s) [V πθ (s)]. Hence, the objective is to find a policy π∗(a|x, φ) as close as π? where 〈π∗, φ∗〉 ∈ W(G), that maximizes the first objective U(w). The policy π∗ can be broken down by the ideal policy π? and a wrong policy π′ 6= π? as follows,
π∗(a|x, φ) = Eqφ(s|x) [π ?(a|s)]
= qφ(s0|x)π?(a|s0) + (1− qφ(s0|x))π′(a|φ,x), (14) for the observations x ∈ Xn, where s0 ∈ S is the true state. Hence,
V π ∗ (s0|φ) = EP(x|s0) [qφ(s0|x)V ?(s0) + (1− qφ(s0|x))V ′(x|φ))] = qφ(s0)V ?(s0) + EP(x|s0) [(1− qφ(s0|x))V ′(x|φ))]
= qφ(s0)V ?(s0) + (1− qφ(s0))V̄ ′(s0|φ), (15)
where,
V ′(x|φ) := ∫ R1(s0,a) n∏ i=1 dπ′(ai|s)qφ(s|x), (16)
and
V̄ ′(s0|φ) := EP(x|s0) [ V ′(x|φ)1− qφ(s0|x)
1− qφ(s0)
] . (17)
Thus, the error from the ideal value function can be written as follows, V ?(s0)− V π ∗ (s0|φ) = (1− qφ(s0))(V ?(s0)− V̄ ′(s0|φ)). (18)
The error is minimized if qφ(s0) = 1 as V ?(s0) > V̄ ′(s0|φ) by the definition. From the Jensen’s equation,
logEp(s0) [qφ(s0)] ≥ Ep(s0) [log qφ(s0)] = −DKL (p || qφ)−H [p] . (19)
Therefore, the right-hand side determines the lower bound of the probability to be maximized, Ep(s0) [qφ(s0)]. As the second term does not depend on φ, the optimization is achieved by minimizing DKL (p || qφ).
Suppose that J(〈π, φ〉;G) = Ĵ(G) > J∗(G) for a non-truthful reporting policy such that σφ(h|h) < 1. From lemma A.1, qφ(s|hi) for an internal state hi = f(xi) of Agent i with an encoder f minimizes DKL (p || qφ(s|hi)). However, as qφ(s|zi) 6= qφ(s|hi), DKL (p || qφ(s|zi)) > DKL (p || qφ(s|hi)) holds. That contradicts the Pareto-optimally. Therefore, σφ must be truthful.
Next, since σφ(h|h) = 1 holds from the assumption of strong truthfulness, from the symmetry ofR, Eq (12) and (13) are written as follows.
Ĵ = sup θ,φ J = sup θ,φ Ep(s) [nV πθ ] = sup θ,φ
∫ nV πθ (s) dp(s)
= sup θ,φ
∫ nV πθ (s) dqφ(s|h1, z−1) n∏ j=2 dσj(zj |xj) dP(xj |s) dp(s)
= sup θ,φ
∫ nV πθ (s) dqφ(s|h) dPn dp
= sup θ,φ
∫ nR1(s,a) dπnθ (a|s) dqnφ(s|h) dPn dp. (20)
Proposition A.2. If [C] is an unbiased truthful mechanism of G, self-play with G[C] converges to Ĵ(G).

heading: Proof.
text: Since [C] is unbiased, Eπθ [Ci] = 0 holds. Hence, for an arbitrary baseline b, b+ Ci 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̂(G[C]) = Ĵ(G) holds from Proposition A.1. A general loss function `ψ : A × Z → R∞ for any strictly concave nonnegative function ψ : P(A)→ R∞ is defined as follows:
`ψ := Dψ (πθ(aj |zi)‖δ(aj |·)) , (21) where δ(aj |·) is a point-wise probability that satisfies lim →0 ∫ B( ;ãj)
dδ(aj |ãj) = 1 for an open ball B( ; ãj), and Dψ is Bregman divergence (Bregman, 1967) defined by the following equation.
Dψ(p‖q) := ψ(p)− ψ(q) + ∫ ∇ψ(q) d(p− q). (22)
Sending a truthful signal is the best response to minimize the expectation of the general loss function. For example, KL-diveregence is a special case of Bregman divergence when ψ = −H [·], and the following equation holds.
Eπθ [`ψ] = ∫ Dψ (πθ(aj |zi)‖δ(aj |·)) dπθ(aj |hi)
= DKL (πθ(ai|zi) || πθ(ai|hi)) ≥ 0. (23)
The equality holds if and only if zi = hi. Notice that πθ(ai|hi) = πθ(aj |hi). Now, we generalize the zero-one mechanism to arbitrary signaling games.
Proposition A.3. (Bregman mechanism) For any signaling games, if supφ ‖ dV πθ/dβIψ‖ < 1, [ıIψ] is an unbiased truthful mechanism of G ∈ G for a general cost function:
Iψ(a|z) := ∆Lψ(a|z)1 = n− 1 −1 . . . −1 −1 n− 1 . . . −1
... ...
. . . ...
−1 −1 . . . n− 1
 ·  0 `ψ(a2|z1) . . . `ψ(an|z1) `ψ(a1|z2) 0 . . . `ψ(an|z2)
... ...
. . . ...
`ψ(a1|zn) `ψ(a2|zn) . . . 0
 
1 1 ... 1  , (24) where ∆ := nE − 11T is a graph Laplacian.

heading: Proof.
text: The problem we dealt with is 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) properness, the score should be maximized if and only if the information is true. The well-known example of the scoring rule is mutual information (MI), which compares a pair of probabilistic distributions p and q 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 a set Ω, F(·‖·) : P (Ω) × Ω → R∞ is a regular proper scoring rule iff there exists a strictly concave, real-valued function f on P (Ω) such that
F (p‖x) = f(p)− ∫
Ω
f∗(p(ω), x) dp(ω) + f∗(p, x) (25)
for p ∈ P (Ω) and x ∈ Ω, where f∗ is a subgradient of f that satisfies the following property, f(q) ≥ f(p) + ∫
Ω
f∗(p, ω) d(q − p)(ω) (26)
for q ∈ P (Ω). We also define F for q ∈ P (Ω) as F (p‖q) := ∫
Ω F (p‖x) dq(x), and describe a set
of regular proper scoring rules B.
For F ,F1,F2 ∈ B, the following property holds (Gneiting & Raftery, 2007).
1. Strict concavity: if q 6= p, then F(q‖q) > F(p‖q). 2. F1(p‖q) + aF2(p‖q) + f(q) ∈ B where a > 0 and f are not dependent on p. 3. −Dψ ∈ B, where Dψ is the Bregman divergence.
Lemma A.2. For any F ∈ B and a function `F defined as shown below, if supφ ‖ dV πθ /dβ`ψ‖ < 1, then [ı`F ] is a truthful mechanism of G.
`F (aj |zi) := { −F (πθ(aj |zi)‖aj) (i 6= j) 0 (i = j) . (27)
Proof. We prove that the surrogate objective of G[ı`F ], V πθβ := V πθ − β`F is strictly concave, and if ∇φV πθβ = 0, then zi = hi with probability 1. We denote φ̂ as the truthful parameter where σφ̂(hi|hi) = 1. The policy gradient for φ is
∇φV πθβ dqφ =∇φV πθ dqφ + β∇φ ∫ F (πθ(aj |zi)‖aj) dπθ dqφ
=∇φV πθ dqφ + β∇φF (πθ(aj |zi)‖πθ(aj |hi)) dqφ. (28)
First, we consider the local optima, i.e., ∇φV πθ dqφ = 0 and φ 6= φ̂. For Gâteaux differential with respect to ~φ := (φ̂−φ)T/‖φ̂−φ‖, ~φ∇V πθβ = β ~φ∇`ψ > 0 holds from the strict concaveity. At the
global optima i.e., ∇φV πθ dqφ = 0 and φ = φ̂, ∇φV πθβ = β∇`ψ = 0 holds. Next, if ~φ∇V πθ < 0, as supφ ‖dV πθ / d`F‖ < β, the following equation holds for φ 6= φ̂.
~φ∇V πθβ dqφ = ~φ (∇V πθ + β∇`F ) dqφ
> ~φ∇V πθ dqφ + sup φ ∥∥∥∥ dVd`F ∥∥∥∥ ~φ∇`F dqφ
≥ ~φ∇V πθ dqφ − inf φ (~φ∇V πθ ) dqφ ≥ 0. (29)
Hence, ~φ∇V πθβ ≥ 0 holds, and the equality holds if and only if φ = φ̂. Therefore, V πθ β is strictly concave, and the following equation holds for αk ∈ o(1/k).
lim K→∞ K∑ k=1 ∇φV πθβ (φk) ‖∇φV πθβ (φk)‖ αk = φ̂. (a.s.) (30)
Iψ is defined for both discrete and continuous actions. Table 3 lists examples of scoring rules `ψ for arbitrary actions. In particular, minimizing `ψ for continuous action is known as probability density estimation (Gneiting & Raftery, 2007).
−Iψ is a proper scoring rule (Gneiting & Raftery, 2007) since it is a linear combination of Bregman divergence. Hence, from Lemma A.2, [iIψ] is truthful. Besides, since 1TIψ = 1T∆Lφ1 = 0, [iIψ] is unbiased. 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,
sup φ ∣∣∣∣∂ ReV πθ∂ ImV πθ ∣∣∣∣ < β, (31)
where β <∞ is bounded mass parameter.

heading: Proof.
text: From Proposition A.3, [ıIψ] is unbiased truthful. Therefore, from Proposition A.2, convergence to the global optima is achieved.

heading: A.2 SELF-PLAY CONVERGES TO LOCAL OPTIMA
text: Theorem A.2. If G ∈ G is non-truthful, self-play does not converge to the global optimum Ĵ(G).

heading: Proof.
text: Example A.1. (One-bit two-way communication game) Fig. 4 shows an example of a non-cooperative partially observable environment with 1-bit state. The reward structure is presented in Table 4. The sum of rewards is maximized when both agents report the correct state to the environment,
n∑ i=1 Rni (s,a) = { 2c (a1 = a2 = s) 0 (otherwise) .
Hence, the objective varies in the range 0 ≤ J(G2com) ≤ 2c.
Proposition A.4. If c < 1, J∗(G2com) < Ĵ(G2com) holds.

heading: Proof.
text: Since p(s) = 1/2, we can assume s = 1 without loss of generality. Besides, we discuss only Agent 1 because of symmetry. From Z = {0, 1}, Agent 1’s messageling policy σ1 sends the correct information x or false information 1 − x when it knows x. Hence, we can represent the policy by using parameter φ ∈ [0, 1] as follows.
σφ(z|x) = { φz(1− φ)1−z (x = 1) 1/2 (x = ◦) , (32)
Differentiating σφ with φ gives the following.
dσφ dφ = { 2z − 1 (x = 1) 0 (x = ◦) G 2 com. (33)
Therefore, from Eq (13), if 〈π∗, ·〉 ∈ W∗(G2com), then the policy gradient for φ is as follows. d
dφ U(π∗, φ) =
d
dφ
∫ V ∗1 dq1 dσ1 dP dp = ∫ V ∗1 dq1
dσ1 dφ dP dp
=λ ∫ V ∗1 (2z1 − 1) dz1 ∣∣∣∣ s=x1=1
=λ ∫ (2z1 − 1)R1 dπ∗1 dπ∗2 dq2 dz1 dP ∣∣∣∣ s=x1=1
=λ(1− λ) ∫ (2z1 − 1)R1 dπ∗1 dπ∗2 dq2 dz1 ∣∣∣∣ s=x1=1,x2=◦
=λ(1− λ) 1∑
z1=0
(2z1 − 1)R1(s, 〈x1, z1〉) ∣∣∣∣∣ s=x1=1
=λ(1− λ) [R1(1, 〈1, 1〉)−R1(1, 〈1, 0〉)] =λ(1− λ)(c− 1) < 0. (34)
As the policy gradient is negative from the assumption of c ∈ (0, 1), φ∗ = 0 gets the Nash equilibrium from φ ≥ 0, thereby resulting in always sending false information to the opposite:
σφ∗(z|x) = {
1− z (x = 1) 1/2 (x = ◦) . (35)
Let J〈x1, x2〉 := J |x=〈x1,x2〉. We can get J∗ and Ĵ as follows.
J∗ = ∫ J∗〈x1, x2〉dP2 dp
= J∗〈1, 1〉λ2 + J∗〈1, ◦〉 · 2λ(1− λ) + J∗〈◦, ◦〉(1− λ)2
= 2cλ2 + 0 + 2c/22 · (1− λ)2
= 2c [ λ2 + 1
4 (1− λ)2
] , (36)
and
Ĵ = ∫ Ĵ〈x1, x2〉dP2 dp
= Ĵ〈1, 1〉λ2 + Ĵ〈1, ◦〉 · 2λ(1− λ) + Ĵ〈◦, ◦〉(1− λ)2
= 2cλ2 + 2c · 2λ(1− λ) + 2c/22 · (1− λ)2
= 2c [ λ2 + 2λ(1− λ) + 1
4 (1− λ)2
] , (37)
respectively. Therefore, Ĵ − J∗ = 4cλ(1− λ) > 0, and J∗ < Ĵ holds. From Proposition A.2, G = G2com is the counterexample that global optimally does not occur.
A.3 ZERO-ONE MECHANISM SOLVES G2com .
Proposition A.5. (zero-one mechanism) Let ` : A × Z → {0, 1} be a zero-one loss between an action and a message `(ai|zj) := aj(1− zi) + (1− ai)zi, and
I(a|z) := [
1 −1 −1 1
] [ 0 `(a2|z1)
`(a1|z2) 0 ] [ 1 1 ] . (38)
If β > (1 − c)(1 − λ)/λ, then [iI] is an unbiased truthful mechanism of G2com, and self-play with G2com[ıI] converges to the global optima Ĵ(G2com) = 2c[1− 3/4 · (1− λ)2].

heading: Proof.
text: The following equation holds. d
dφ V ∗β,1 dq1 =
d
dφ
∫ (V ∗1 − βI1 dπ∗2 dq2) dq1
=− λ(1− λ)(1− c)− β ∫ I1 dπ∗2 dq1 dq2
dσ1 dφ dσ2 dP2 dp
=− λ(1− λ)(1− c)− βλ ∫ I1 dπ∗2 dq2(2z1 − 1) dz1 dσ2 dP ∣∣∣∣ s=x1=1
=− λ(1− λ)(1− c)− βλ2 ∫ (2z1 − 1)`(a2|z1) dπ∗2 dq2 dz1 ∣∣∣∣ s=x1=x2=1
=− λ(1− λ)(1− c)− βλ2 1∑
z1=0
(2z1 − 1)`(1|z1)
=− λ(1− λ)(1− c)− βλ2(`(1|1)− `(1|0)) =− λ(1− λ)(1− c) + βλ2
=λ2 [ ı− (1− c)1− λ
λ
] . (39)
Therefore, if β > (1− c)(1− λ)/λ, then φ∗ = 1 holds, and J∗ = Ĵ holds. The value of Ĵ is clear from the proof of Lemma A.2.
[ıI] is also known as the peer prediction method (Miller et 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. 4 Right.

heading: B COMPLEXITY ANALYSIS
text: Although the computational complexity of βIψ per iteration is O(n3) as it involves the multiplication of n-order square matrices, we can reduce it to O(n2) to obtain Iψ = nLψ − 1TLψ1. The spatial complexity is O(n2), and the sample size is O(n).

heading: C EXPERIMENTAL ENVIRONMENTS
text: In the experiment, we 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. 1 shows the environments.

heading: C.1 PREDATOR PREY (PP)
text: Predator-Prey (PP) is a widely used benchmark environment in MARL (Barrett et al., 2011; 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 is necessary to inform other predators about the prey’s location and the locations already searched. Thus, the prey’s location is conveyed through communication among the predators, but predators can 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 in a 5× 5 environment. In PP-5, the field of view is set to 1 in a 10× 10 environment. The numbers represent the number of agents.

heading: C.2 TRAFFIC JUNCTION (TJ)
text: Traffic Junction (TJ) is a simplified road intersection task. An n body agent with a 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-way 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 a total of four intersections. Each number corresponds to n.
In the initial state, each vehicle is given a starting point and a destination and is trained to follow a 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 a single time step. It is crucial to ensure that other vehicles do
not approach each other to prevent collision while making good use of multiagent communication. That is similar to blinkers and brake lights.

heading: C.3 STARCRAFT: BLOOD WARS (SC)
text: Explore: In order to complete the exploration task, the agent must be within a 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 is 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 (relative x, relative y, visible), where visiblea is a visual range. If the enemy is not in exploration range, the relative x and relative y are zero. The agent has nine actions to choose from: eight basic directions and one stay action.
Combat: Agents make their own observations (absolute x, absolute y, 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 a visible flag. All observations are normalized to lie between (0, 1). The agent must choose from 9+M actions, including 9 basic actions and 1 action to attack M agents. The attack action is only effective if the enemy is within the agent’s view, otherwise is a no-problem. In combat, the environment doesn’t compare to Starcraft’s predecessors. The setup is much more difficult, restrictive, new and different, and therefore not directly comparable.
In Combat task, we give a negative reward rtime = −0.01 at each time step to avoid delaying the enemy team’s detection. When an agent is not participating in a battle, at each time step, the agent is rewarded with (i) normalized health status at 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 of (i) all remaining health * 3 as a negative reward and (ii) 5 * m + all remaining health * 3 as a positive reward if the agent wins. Give 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-demanding tasks even more difficult.

heading: D HYPERPARAMETERS

Review summaries:
This 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).

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.