Truthful Self-Play
Authors: Shohei Ohsawa
Venue: ICLR 2023 poster (2023)
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.

Published as a conference paper at ICLR 2023
TRUTHFUL SELF-PLAY
Shohei Ohsawa Founder & CEO
Daisy AI
6-13-9 Ginza, Chuo-ku, Tokyo, Japan o0 daisy.... inc
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 in case of multi-agent reinforcement learning in non-cooperative partially observable environments with communication due information asymmetry. Our proposed framework is 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-ae of-the-art performance of our framework.
INTRODUCTION
Evolving culture prevents deep neural networks from falling into bad local optima (Bengio, 20. Self-play (Samuel, 1967; Tesauro, 1995) has not only demonstrated the ability to abstract high- dimensional state spaces as typified by AlphaGo (Silver al., 2017), but also improved exploration coverage in partially observable environments. Communication (Sukhbaatar et al.. 2016: Singh et al., 2019) exchanges their internal representations such as explored observation and hidden state in RNNs. Evolutionary learning is expected to be general framework for creating superhuman Als as such learning can generate 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-play to non-cooperative partially observable environments via mechanism design (Myerson, 1983; Miller et 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 on the signals. We formulate the non-cooperative partially observable environment as an extention of the partially 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.

---

Published as a conference paper at ICLR 2023
As the first contribution, we propose truthfid 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-as 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 Komm-POSe 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. 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) employed in multiagent tasks.
Notation: Vectors columns. Let [n] := {1,- , n). R is set of real numbers. i is the imaginary unit. Re u and Im u are a real and an imaginary part of complex number u, respectively. n-tuple are written boldface of the original variables a (ai,..... an) and a is (n -uple obtained by removing the i-th entry from a. Let 1 == (1,..., 1)T" Matrices are shown in uppercase letters L == (Ley). E is the unit matrix. The set of probability distributions based on the support X' is described as (X)).
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 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(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-POMPP-oom (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

---

Published as a conference paper at ICLR 2023
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- -agent
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 coooperree 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-ddimensional 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, := (zni)) signal from Agent an internal state of i-th agent before receiving the singals from the others. A game in Comm-POSE is denoted as G (n. T, S, A, X, T, P, R, Z).
E gnxn is a signal matrix in which (i,j)-th entry žrij represents a Agent at l. The i-th diagonal entry of Ze, hui == Zuū represents the pre-state,
The objective of Comm-POSG is social welfare (Arrow, 1963) defined by the following,
T
J
: E
(I)
where 7 [] is discount rate, is reward Ti is a stochastic policy, and V is the value function.
In extensive-form games including Comm-POSS 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 + 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)
(Se, Jo. Jø, no), where
3

---

Published as a conference paper at ICLR 2023
fo(h)-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, (z hes) is a stochastic messaging policy for pre-state hy := fa Txs,,
stochastic model for a post-state hes E 2 and the received messages 21 = Z (Ze16).... 1,5; heg 2,, 2tmi)", and
ao(hu 21s)
. (aes (as) is the stochastic action policy with parameter 0.
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 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 hes in the hidden layer of the RNN and the received signals žti from other agents. Hence, the veracity of the signals Zu is the point of contention.
3.3 TRUTHFULNESS
In mechanism design, a truthful game (Vickrey, 1961) is game in which all agents make an honest reporting in the Bayesian Nash equilibrium. Comm-POSGs, the truthfulness of the game is achieved if all the sent signal equals the pre-state žtij = hus i.e., all the agent share complete information. In such case, every agent has the same information 2n = h,, == (hei,-... hen) for all i's and the same post-state model probability distribution, and hence the mean of the cross entropy between the distributions below will be minimized.
(Z,)
= n
Σ
go (oohhslzee)
+ n²
ΣΣ DKL (go(her(ze) ll go (
(2)
The first term represents the entropy of knowledge each agent has about the environment, and the second the information asymmetry between the agents. D& is lower bound on the amount of true information the environment has H [p(+)]] Since achieving truthfulness is essentially the same problem minimizing Dg, it also maximizes J simultaneously.
Proposition 3.1. (global optimality) For any games & in Comm-POSS if Dz = H [p(s:))for ostsT T and R; is symmetric for any permutation of E [[n]]. (G) j(G) holds.
Proof. Let w := (0, on a parameter space W(G), and (G) the BNE. Since J is obviously maximized if os is truthful, we prove dg must be truthful under a given condition. To this end, show the following Pareto-optimality.
Lemma 3.1. For any G in Comm-POSC and given w, if (() J(w') holds for any w' E W(G).
then either of U(w) 2 U(w) DKL (p 1l 90) DKL (p q0) holds, where
U(w)= = Egg [V*0]=
(* (soo 2c, do
(3)
Proof. The first inequality ((w) 2 ((w') indicates that w is on the BNE W given o, and of the second that the belief state d is as close to the true state p as possible. On fully-observable environment, from the theorem of value iteration, there exists the solution x (s.) w.r.t V (s.) for any 8, S. We name x² and V 4* the unbiased policy and value, respectively.
Since the unbiased policy solves the objective as J(w) ((w))nEEp(s) [s)) from Eq (1), the goal intrinsicly to find the policy x* as close as n² for (n* Φ²) W(G), that maximizes U(w). The n further can be represented as a mixed policy made of a couple of the unbiased policy x² and biased policy n' # n² as follows,
n Xxei Ø) (oc( [xr (ats(sti)
(s xrs) (ar (80) + (1 (s000()))))) (aulo) xts),
(4)
4

---

Published as a conference paper at ICLR 2023
for the observations X 2", where 8t0 S is the true state. Hence
W (stol = Ep(x)s+rr)) (10 V (1 (0 x (x))
qo (8(o))) V*)o0)) (seo) + Bp(xu(+10) [[1 -xx (8(()0) ( + (o((mo)) (F(ol))))(((eool))
(5)
where
- R1 a+) II dm' (ans (oo Xts);
a
V'(x(()) = M1 arEd
(6)
and
V'(xul0) 1 (0( xcii)
('(swlo) := (x(sso)
(31))
Thus, the enror from the unbiased value function can be written as V* (8:0) - V" Φ) = (1
Is (e())))((V (sto) - (o)) which minimized if qo($1)) = as V (8t0) (stol by the
definition. From the Jensen's ss equation,
log Ep(ss) (so() 2 B((s)) [log go (
- DK.. (p (6)
H [p]
(8)
The right-hand side of the inequation corresponds to the negative cross-entropy to be maximized. Therefore, as the second term [p] depends not on ø, the optimization is achieved by minimizing DKL (p 9p). O
Suppose that ( J(w)= > (G) for a non-truthful reporting policy s.t. (h(h))) 1. From lemma 3.1, go(s) for an internal state hy f(zss) of Agent with an encoder f
minimizes DKL (p (o(s) he))) As that (s * [s(ss)he) and DKL (p ll (0(5))2)))
DKL. (p (h(s))) contradicts the Pareto-optinn paneto-optimality, dg must be truthful. D
PROPOSED FRAMEWORK
An obvious way to achieve truthful learning is to add D& as penalty term 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 D3 contains the agent's internal state, post-state h so the exact amount cannot be measured by the designer of the learner. post-states are reported correctly, then pre-states should also be reported honestly, and thus truthfulness is achieved. Therefore, 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 introduction of peer prediction method (Miller et al., 2005), truthful mechanism 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 the global optimum in Comm-POSG. We show the whole procedure in Algorithm 1.
Comm-POSG, and the other is the
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. environments, including CoSm-POSG, 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 the complex rewards are ordered by the mass parameter 3 during training, which allows the weights of the network maintain a real structure.
5

---

Published as a conference paper at ICLR 2023
The whole imaginary reward is denoted as iY = (dyoy (djl)) where üyy 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 7; as i)-th entry. We write g 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 [[T)] is truthful and R is an Hermitian matrix, (G(( J(G) holds.
Proof. Since g[i is truthful, (9( J(gliY) holds from Proposition 3.1, Further, since R is Hermitian, ayss = -éyje. and hence Im [Gg]YY] = holds; J(gliY]) = J(G) holds. O
This indicates that the BNE could be improved by introducing imaginary rewards: (G(Y)) > from the condition that R+ is Hermitian, the imaginary rewards affect not the social welfare of the system, which a macroscopic objective, but only the expected rewards of each agent. The baseline in policy gradient (Williams, 1992) is an example of a function that affects not the objective 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 a meaningful quantity only when n 2 2 and is not observed when n 1.
(G). Also, since - ddjsj
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 encourage verifiers 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 verifier.
The general scoring rule can be expressed as F(p,l(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 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(pell = log Ps. where the expected value for a 1-bit signal is the cross-entropy P log Pa + (1- p?) log( 1 Ps) for belief p.. One can find that pe P is the only report that maximizes the score.
Since the proper scoring rule assumes that events s 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 updated by the signal, rather than the event. This concept is formulated by a model that assumes that an event emits 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 F(p(s (p((spp (22 [[)] 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 as ~ Tols; for the true state s; E S. In 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 Prmm--OOSG 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 L, as follows,
Le = (E(an) Ezji (tji)) [m]); E(jnlF(j)) == ((m Regi) ||a.)) log (anll)))))))
(9)
which is an n-order square matrix representing the score from Agent to Agent j.
4.3 THE TRUTHFUL SELF-PLAY
In TSP, truthful system is constructed by introducing a proper scoring rule into imaginary rewards. However, since the score matrix obtained from the proper scoring rule does not satisfy Hermitianity, perform zero-averaging by subtracting the mean of the scores from each element of the matrix,
Note the use of for imaginary units and for indices.

---

Published as a conference paper at ICLR 2023
Algorithm 1 The truthful self-play (TSP).
Require: Comm-POSG 9 (n. S, A.T.P.R*). recurrent neural network (as 1o: mo)
with initial weight Wo (fo: σo) and initial state hg, learning rate
0, and mass parameter
8 820 O.
Initialize w < Wo- for each episode
Genesis: 81 ~ p(s), hos + ho V [n]]
for t = 1 to 7 do
1. Self-Play
Observe
X₁ ~ P)(((se),
Update pre-state
hu - fo -o T(i),
e
Generate message
Ziz Jol (-
Vi [
Send message
Z. + (Zel,..., Bin)
Receive the message
Vi E [n]
Update post-state
hu (-(.111))
vi E [n]
Act
To (ee))
Vi E [n].
Get the real reward
r 5- ((, ay);
2. Compute the score matrix with peer prediction mechanism (Miller et al., 2005),
log (a()(t))
(i j) Vi,j [n]]
(12)
3. Combine real and imaginary rewards and construct complex reward.
R
+IC.
(13)
4. Update the weights by policy gradient (Williams, 1992).
g:
(an) log (a + log (hus (a)) log o (21 (2
(14)
+ a Re g: agTmge
5. Proceed to the next state 8L-1 ~ T(-)),,
end for end for return
thereby making the sum to zero. This can be expressed as follows using the graph Laplacian = E 11 /n.
n
(a(aaaz))) 0
Lo 2n) Ex (een 212)
n
e (acs (2e2)
Y AC =
-1
n-1
(p(aralzan)
(arzl(ze)))
(IO)
get
R R+=R+iAC,
(11)
which is the formula that connects reinforcement learning and mechanism design.
We show the trathful self-play (TSP) in Algorithm 1. The only modification required from self-play the imaginary reward.
Theorem 4.1. (global optimality) For any G in Comm-POSG, TSP converges to the global optimum (g) if the following convergence condition are met,
Re V
sup
< 8
(15)
mm Vse
7

---

Published as a conference paper at ICLR 2023
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 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
where B < 3o is bounded mass parameter.
Proof (in summary²) From Proposition A.2, [3ACy] unbiased truthful. Therefore, from Proposition A.I, convergence to the global optima is achieved.
5 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) in which predators with limited vision look for a prey on square grid. (b) traffic junction environment (TJ) similar 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
Visual mage
possible
New anivals
l'riend
Enemy
Ctr extting
Figure Experimental environments. a: Predator Prey (PP-n) (Barrett al., 2011). Each agent receives -0.05 at each time step. After reaching the prey, they receive rı: 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 r. -0.05 at each time as an incentive to run faster. If cars collide, each car involved in the collision will receive Tas -1 c: Combat task in StarCraft: Blood Wars (SC) (Synnaeve et al., 2016).
We compare the performances of TSP with self-play (SP) and SP with curiosity (Houthooft et al., 2016) using three tasks belonging to Comm-POSE 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 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
Refer Section for the pronfs.
8

---

Published as a conference paper at ICLR 2023
-2.0
-150
26
522
120
1230
1093
200
600
600
3008
3200
1400
8
Figure 2: Learning curves in three-agent predator prey (PP-3). a Truthfulness, the fraction of steps that the agent shares true pre-state (Zig = h₂), b the real part of the reward, and c 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 TOMedic 50
1.592 0.169
2.276 1 1.427
1.364 + 0.107
Combat-10Mv3Ze 50
3.202 = 1.382
3.815 = 0.392
1.717 + 1.548
(b) confirms that the social welfare of TSP exceeds that the SPs. (c) confirms that the average of the imaginary part is zero. From these experimental results, conclude that the TSP successfully realized truthful learning and state-of-the- in tasks comprising 3 to 20 agents.
StarCraft: Table 2 shows comparison of social welfare in the exploration and combat tasks in StarCraft. (i) In the search task, 10 Medics find one enemy medic on 50x50-cell grid; similar to PP, the reward is 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 50 cell grid. The maximum step of the episode is set at 60. We find that IC3Net, with its information-hidee -hiiinnniiiiiiiiiin gate, performs less well than CommNet but performs better when trained in TSP due to the truthful mechanism.
CONCLUDING REMARK
Our objective was to construct 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 to 20 agents and achieved the state-of-the-at performance for the tasks. Herein, we summarize 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 iAC 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 Py PyTorch.
3. Broad coverage: TSP a general framework, the same as self-play. Since TSP is indepen- dent of both agents and environments and supports both discrete and continuous control, it 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 developed by using the methodology employed in this study.
9

---

Published as a conference paper at ICLR 2023
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. 18X3v:1803.10122. 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- bapeed deep reinforcement learning. arXiv:/8077 0/28/, 2018.
10

---

Published as a conference paper at ICLR 2023
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.
Nolan Miller, Paul Resnick, and Richard Zeckhauser. Eliciting informative feedback: The peer- prediction method. Management Science, 51(9):335-1173 2005.
Roger 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 L Samuel. Some studies in machine learning using the game of checkers. ii recent progress.
IBM Journal of Research and Development, 1(6))601-617, 1967.
Amartya Sen. Collective choice and social welfare. Harvard University Press, 1984.
David Silver, Julian Schrittweeser Karen Simonyan, loannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. Mastering the game of go without human knowledge. Nature, 550(7676):354359, 2017.
David Silver, Thomas Hubert, Julian Schritwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Mare Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, et al. general reinforcement learning algorithm that masters chess, shogi, and go through self-play. Science, 362(6419): 1140-1144, 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 arXiv: 0ete:/111.002,.. 2016.
Christian Szegedy, Wojeiech Zaremba, llya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. In ICLR, 2014.
Yichuan Tang. Towards learning multi-agen agent- negotiations via self In ICCV,
Gerald Tesauro. Temporal difference learning and td-gammon. Communications of the ACM, 38(3): 58-68, 1995.
William Vickrey. Counterspeculation, auctions, and competitive sealed tenders. The Journal of Finance, (6(1):8-37) 1961.
Ronald J Williams. Simple statistical frllient- algorithms for connectionist reinforcement learning. Machine learning, 8(3-4):229-256, 1992.
11

---

Published as a conference paper at ICLR 2023
A THEORY
a human brain can learn such high-level abstractions if guided by the messages produced by other humans, which act hints indirect supervision for these high-level abstractions; and, language and the recombination and optimization of mental concepts provide 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)
Proposition A.1. If [C] is an unbiased trathful mechanism of G, self-play with gIC] converges to (g)..
Proof.
Since [C] is unbiased, Ex, [C:] = O holds. Hence, for an arbitrary baseline 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"(C((]) J(G[C)) (g) holds from Proposition 3.1.
A general loss function Eyp A x Z -> Re, for any strictly concave nonnegative function x ((A) + RS is defined as follows:
bu = De
(16)
where 5(azl-) is a point-wise probability that satisfies lim,-so B(esay) dō(a, (ūy) = for an open ball B(e;ūg)) and Da is Bregman divergence (Bregman, 1967) defined by the following equation.
(pll)) = xpp) vb()) / (()
(17)
Sending a truthful signal the best response to minimize the expectation of the general loss function. For example, KL-diveregence is special case of Bregman divergence when d -H [-], and the following equation holds.
EN [cal = / Do (To (To(a,)2)))) dmo(ay(h.)
DKL. (To(as)z;) ll (a h4a) 2 0.
(18)
The equality holds if and only if 24 h4. Notice that (o(a; To To(ay)h4). Now, we generalize the zero-one mechanism to arbitrary signaling games.
Proposition A.2. (Bregman mechanism) For any signaling games, if sup, |d /d3Ipl < 1,
[IT+} is an unbiased truthful mechanism of E 6 for general cost function:
(alz) = (alz))
1 -1
(a212))
Ev (a 21) L (222
1
n
(a112))
(19)
:
0
n n-1
ev(alkza) (p(a2lzn)
where A = n. 11 is graph Laplacian.
Proof.
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 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 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.
12

---

Published as a conference paper at ICLR 2023
Definition A.1. (Gneiting & Raftery, 2007) For set Q, F(-ll-) B (2) S - B. is regular proper scoring rule iff there exists a strictly concave, real-valued function on & (S2) such that
f(v) J f (p(w), dp(w) (p.
F(ll(z)
(20)
for E + and x E Q2 where f* is subgradient of f that satisfies the following property,
f(a) f(0) / l (p,w) d( p) (w)
(21)
22
for q & (2). We also define F for q 2 (9t) F (xllg) Jn F (pl(z) dq(x)), and describe set of regular proper scoring rules B.
For F, F2 B, the following property holds (Gneiting & Raftery, 2007).
1. Strict concavity: if # p. then F(all4) > F(pllg).
2. Fi (plla) + (F + f(g)= B where > 0 and f are not dependent on
3. >D E B, where D is the Bregman divergence.
Lemma A.1. For any B and function E defined as shown below, sus /VV//d then [ is truthful mechanism of G.
(0 ( (T(((((()=))))
(i (i j)=
(x(a)1z))=
(22)
Proof. We prove that the surrogate objective of G(e.)). V/3e == V - BBl is strictly concave, and
VoV then z; hú with probability We denote a as the truthful parameter where T (hg = 1. The policy gradient for is is
V V dgs + B V / F (Ta(a))<)lag) dag dgo
Vo 3 dop
V n dgø + V oF
dgs-
(23)
First, we consider the local optima, i.c., V0\*' dg. = 0 and Φ + Ô. For Gâteaux differential with
respect H (e x) / e o VV 3Φ Vp > 0 holds from the strict concaveity. At the
global optima i.e., V V dq. 0 and â. V 3 Ve 0 Next, if Ø VV= 0. as s || dV de < B, the following equation holds for * G.
/ V dgs = क VV== + (VF) dgp
dV
o T dgo + sup
Vl dgs
de
0. o V dgo - -nf Te dgs
(24)
Hence, 3 VV > 0 holds, and the equality holds if and only d S. Therefore, V is strictly concave, and the following equation holds for ag E (1/k).
K
V (ox)
lim HOO
V To (ox)) as = -. (a.s.)
(25)
Is is defined for both discrete and continuous actions. Table lists examples of scoring rules e,p for arbitrary actions. In particular, minimizing Ep for continuous action known as probability density estimation (Gneiting & Raftery, 2007).
-I, a proper scoring rule (Gneiting & Raftery, 2007) since is a linear combination of Bregman divergence. Hence, from Lemma A.1, [iIp]] is truthful. Besides, since 1 ITI.p. = A = 0, [iZz] unbiased. 0
13

---

Published as a conference paper at ICLR 2023
Table 3: Examples of the scoring rules, where k > 1, |pll. = (J p(a)) (a)a))daa)44 dx) Readers can refer to
(Gneiting & Raftery, 2007) for examples of many other functions.
A
Z
x(p))
( 2)
Zero-one
Discrete
Discrete
T (a
Logarithmic
Discrete
Continuous
[p]
log (T(
Quadratic
Discrete
D/C
EeeA p(a) -1
2m²(a - ( [=))
(Brier, 1950)
Continuous
DIC
11p13
2 - T
Pseudospherical
Discrete
Continuous
A ((()))) //x
Ta(a|2)* 6- (
(Good, 1952)
Continuous
Continuous
p 1-1
To(a ) n no K-11
T1
12
21
(22
22
Figure 3: Left: One-bit two-way communication game P.om = A
{0, 10, Su
and p(s) = 1/2. Agents are given correct information from the environment with probability of > 0: P(sss) = X, P(ols) = x. 9:(5 z., 2ÿ) follows a Bernoulli distribution and estimates the state p(s) of the environment from observations and signals 2j Z = X. Let h2 Hz. Right: An example of the non-cooperative solutions: s = 1, x (o, 1), z = (o, 0), a = (0, 1), (-1, (-1,1) and
72 2c.
Theorem A.1. (global optimally) For any 9 Comm-POSG, TSP converges to the global optimum [g) if the following convergence condition are met,
Re V
sup
< 3,
(26)
Im V
where 3 < oo bounded mass parameter.
Proof.
From Proposition A.2, [iZa]] is unbiased truthful. Therefore, from Proposition A.1, convergence to the global optima is achieved. D
A.1 SELF-PLAY CONVERGES TO LOCAL OPTIMA
Theorem A.2. lfg E 6 is non-truthful, 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 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,
[2c
(a) 02 = s) (otherwise)
Σ R
Hence, the objective varies in the range 0 < ( < 2c. Proposition A.3. Ifc 1, J (G (( holds.
Proof.
14

---

Published as a conference paper at ICLR 2023
Table 4: Pcom 's reward function (s,
a). C O is a constant that determines the nature the game.
d2
True
False
(21,
(c, c)
(1,
1 8
(-1,1)
(0,0)
without loss of generality. Besides, we discuss only Agent because of symmetry. From Z {0, 1}. Agent I's messageling policy 0₁ sends the correct information or false information - z when it knows æ. Hence, we represent the policy by using parameter Φ E [0, 1] as follows.
Since p(s) 1/2, we can assume
{ [d 0)²-=
(x 1) (x = o)
(<(2/x)
(27)
1//2
Differentiaaingg os with @ gives the following.
do [2a-1
(I = 1)
dø 10 (x= o) Poom.
(28)
Therefore, from Eq (??), if (x",)) E W (C..m) then the policy gradient for á is as follows.
c U(
d
d
/ Vi du do dP dP
Vi dq
dø dP
dø
dø
dø
=x
1/" (2z1 - -1)
==2==1
=1 / (221 -1)R2 d drž dq2 dæ dP
s=n==
=A(1 - A) / (221 (221--1) (221-1)84 1)R2 d drž dg2 d21
12220
1
=X(1 - A) Σ (221 1)R2(s, 21)
=1
$=01=1
=X(1 A) (L, R2, (1,
=A(1 - 1)) <0.
(29)
As the policy gradient is negative from the assumption of e E (0. 1), o= = 0 gets the Nash equilibrium from o 2 0, thereby resulting in always sending false information to the opposite:
{1
(x
p (2|xx)
(30)
1/2
(
Let ((11 x2) = J Jxx=((n
We can get J and j as follows.
J= / J (2), dp dp
J', 1)X² + J" 2X(1 A) ('(0, 2)2
= =ee2 +0+ 200222+20/2 (1- (1
2c x2 (1 2)2
1
(31)
15

---

Published as a conference paper at ICLR 2023
and
j j= / 22) dp²
J(1, 1),2 + J(1, 2X(1 - +) J( o) 2)2
2c + 20-2211--- X) + +2c/22 (1 - 1)²
2c X² +2 A) + 4 ))²
(32)
respectively. Therefore, - J 4cA(1 - X) > 0, and J j holds. 0
From Proposition A.I, G G is the counterexample that global optimally does not occur.
A.2 ZERO-ONE MECHANISM SOLVES Poom
Proposition A.4. (zero-one mechanism) Let L A 2 + {0, 1} be zero-one loss between action and a message ((a:)zz) : aj(1 zi) + (1 - ai)zi. and
I(alz) 1 _
((01122) { (122)1)
(33)
JF3 > (1 c1 A)/,, then [iZ] is an unbiased truthful mechanism of Poom and self-play with G [I] converges to the global optima I( = 2c(1 - -3/4 }
Proof.
The following equation holds.
d V dg
d dΦ / (Vi BI, d d92) dqp
dø
d =- - 1)(1 cc) -B / Iı dmp dq dg2
do² dp2 dp
dø
=-1(1 - A)(1 c)) -BA / In diz dg2(221 - 1) d2g do dP
s=m==
((2a 1)((22)21) d d4z dzj
= - -)(1-c) BX²
s=b==/==
A(1 - A)(1 -) -3A Σ (221 - 1)((1[z1)
21
X(1 A)(1 c) (X²(E(1 E(110))
X(1 A)(1 -) 3X
=>² (1 (1-c) 1-
-
(34)
Therefore, if > (1-c)(1 A) A,, then 6- holds, and J = holds. The value of j is clear from the proof of Lemma A.
[1Z] 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. 4 Right.
B COMPLEXITY ANALYSIS
Although the computational complexity of BI.. per iteration is O(n²) as involves the multiplication of n-order square matrices, we can reduce O to obtain Iς nLg 1 The spatial complexity is Onn²), and the sample size is O(n).
16

---

Published as a conference paper at ICLR 2023
8
T1
12
22
True
False
Unohserved
1
(c,c)
(c+ B, ()
(c,c)
21
(c
3, ())
(c,c)
(1,-1)
01
02
(c,
(-1,1)
(c/4,c/4)
21
1
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(s,, (26
C EXPERIMENTAL ENVIRONMENTS
In the experiment, we used two partial observation environments. This setting is the same as that adopted in existing studies (Sukhbaatar 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 view. The field 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 's location and the locations already searched. Thus, the prey's '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 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 10 environment. The numbers represent the number of agents.
C.2 TRAFFIC JUNCTION (TJ)
Traffic Junction (TJ) is a simplified road intersection task. An n 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-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
In the initial state, each vehicle is given starting point and a destination and trained to follow a determined path as fast possible while avoiding collisions. The agent is in each body and takes two actions, i.c., accelerator and brake, in a single time step. It is crucial to ensure that other vehicles do not approach each other 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 to complete the exploration task, the agent must be within a specific range (field of view) the enemy unit. Once the agent is within the enemy unit's field of view, 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 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 's (absolute absolute y) and the enemy's (relative relative y, visible), where visiblea is a visual range. If the enemy is not in exploration range, the relative x and relative zero. The agent has nine actions choose from: eight basic directions and one stay action.
17

---

In Combat task, we give a negative reward Ptime 0.00 at each time step to avoid delaying the enemy team's 's detection. When an agent is not participating in a battle, at each time step. the agent is rewarded with (i) normalized health status 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 negative reward and (ii) 5 health to all living enemies as a negative reward when you lose. In this task, a group of enemies is tasks Published as a conference paper at ICLR 2023
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 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 It compare to Starcraft's predecessors. The setup is much more difficult, restrictive, new and different, and therefore not directly comparable.
Combat:
current and previous time step, and (ii) normalized
all remaining health 3 positive reward if the agent wins. Give
randomly initialized in half of the map. Thus the other half making communication-deeaande even more difficult.
D HYPERPARAMETERS
Table 5: Hyperparameters used in the experiment, / are grid searched in space {0.1, 1, 10, 100), and the best parameter is shown. The other parameters are adjusted.
Notation
Value
Agents
7
(3, 5, 10, 20)
Observation Internal state
Tt X has E H
R.9
R
Message
Zti
644
Actions
as A
{+, 1 L. - Astop
True state
8, E
{0, 1 225550000
Episode length
T
20
Learning rate
a
0.001
Truthful rate
33
Discount rate
1.0
Metrics
[-]
18


Reviews:
[{"review_id": "wLOl_QnA67", "reviewer": "Reviewer_nN62", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "Paper propose a method for multi-agent reinforcement learning in non-cooperative partially observable environments with communication. The proposed method, TSP, adds imaginary rewards using the peer prediction method by evaluating the validity of information exchanged between agents. TSP has guaranteed convergence to the global optimum and has good empirical performance. \n", "summary_of_the_review": "This work considers multi-agent reinforcement learning in non-cooperative POMDP. The proposed method, TSP, generalizes self-play to non-cooperative partially observable environments via mechanism design. The method has a convergence guarantee and is shown to outperform state-of-the-art performance for various multi-agent tasks. \nHowever, there are some weaknesses that I hope the authors could address in the next version. \n", "strength_and_weaknesses": "Strength\n- This work is novel in the sense that it is the ﬁrst attempt to apply mechanism design to multigent evolutionary learning. \nTSP’s convergence is theoretically guaranteed for arbitrary policies and environments.\n- The method seems relatively easy to implement and numerical experiments show the effectiveness of TSP. \n\nWeakness \n- The authors could add a discussion on what causes self-play + curiosity’s bad performance. \n- The author should at least discuss the scalability since the experiments are on simpler and smaller environments. \n- The learning curves show that TSP is not as stable as baselines, how many random seeds are used in the evaluation? And what causes the instability issue? \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "XZmAS-2kcu", "reviewer": "Reviewer_N5E1", "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": "Truth Self Play (TSP) is a method for improving SP in partially observable environments which involve communication. The motivation is well grounded adding additional reward term to evaluate the truthfulness of communication sent. This is implemented by the additional reward  p(a_j | z_ij), which is to say, force agent j to listen to the communication sent from agent i.  In a reverse way, as the listener has to care about the message, the speaker (as this is self-play) starts providing useful information.", "summary_of_the_review": "The paper is to a good standard and with clarity could be a very high impact paper. Theoretical justifications are great, I would like more experimental analysis and clear terminology to understand implications. ", "strength_and_weaknesses": "## Strengths\n* Strong theoretical grounding\n* Experiments on lots of environments\n* This is useful\n\n## Weaknesses\n* The math is kinda OOT in my opinion. Section 3 could be way shorter. The use of imaginary numbers is unnecesary - simple use R^2 and then apply a normalization over a single dimension.\n* (Figure a) Only showing the Real part of the reward signal?  Can we see how the second reward signal changes over time?\n* Experimental results are lacking. I appreciate the variety of environments applied but simply reporting numbers isn’t convincing. I’d like to understand how messages look with some visualisation and how they change over time.\n* I’d also like to understand what optimal or desired behaviour looks like in these environments - can you get to welface 0 in PP or TJ?\n* Please info the reader more of your baselines (CommNET and IC3Net)\n* Why didn’t you run CommNet w TSP\n* Why don’t you have MAPPO as a baseline?\n* The proper scoring rules seems to be no different agent modelling in other agents. Could you add some of these into the related work section just to help differentiate (or explain in rebuttal if i’m being slow)\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "20MapgE56AK", "reviewer": "Reviewer_bEm1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper presents a general framework named truthful self-play (TSP) which is suitable for communicative partially-observable stochastic games and analytically demonstrates convergence to the global optimum.", "summary_of_the_review": "1. The contribution of this paper is favorable to the community .\n2. The experiment needs improvement to be more convincing.\n3. The language and symbolic descriptions in this paper need to be clearer to avoid misunderstandings.", "strength_and_weaknesses": "Strength\n1. The proposed framework TSP is general and guarantees convergence to the global optimum theoretically and experimentally.\n\nWeaknesses\n1. This paper improves the self-play problem by introducing the 'truthful' reward. However, this paper lacks a full explanation of the meaning of 'truthful', in other words, we do not find relevant information about 'truthful' in the method section, and it is too farcical to use this reward as an inverse game mechanism. The contribution of this paper is too few and its innovation is general.\n2. The experiment needs improvement. \n   1) In Table 1, the effect of PP-5 and TJ-5 is not significantly improved; compared with IC3Net+SP, the value including standard deviation has some coincidence(need more experiments iteration). In TJ-20, there is no reasonable explanation for the reduction of effect variance. \n   2) In Figure 2, the description of (a) is unclear, and the existence of (c) is unnecessary. \n   3) In Table 2, whether the CommNet+TSP's performance can be further improved should be verified. \n3. Spelling problems and unclear statements.\n    1) Introduction para3 pertially -> partially\n    2) The input of function $q_{\\phi}$ is inconsistent, $\\hat{h}_{t i}$ in Section3.2 and $\\hat{h}_{t}$ in Section3.3. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster