Iterated Reasoning with Mutual Information in Cooperative and Byzantine Decentralized Teaming
Authors: Sachin G Konan
Esmaeil Seraj
Matthew Gombolay
Venue: ICLR 2022 Poster (2022)
Keywords: Multi-agent Reinforcement Learning
Cooperation and Coordination
Policy Gradient Optimization
Mutual Information
Iterated Reasoning

Abstract: Information sharing is key in building team cognition and enables coordination and cooperation. High-performing human teams also benefit from acting strategically with hierarchical levels of iterated communication and rationalizability, meaning a human agent can reason about the actions of their teammates in their decision-making. Yet, the majority of prior work in Multi-Agent Reinforcement Learning (MARL) does not support iterated rationalizability and only encourage inter-agent communication, resulting in a suboptimal equilibrium cooperation strategy. In this work, we show that reformulating an agent's policy to be conditional on the policies of its neighboring teammates inherently maximizes Mutual Information (MI) lower-bound when optimizing under Policy Gradient (PG). Building on the idea of decision-making under bounded rationality and cognitive hierarchy theory, we show that our modified PG approach not only maximizes local agent rewards but also implicitly reasons about MI between agents without the need for any explicit ad-hoc regularization terms. Our approach, InfoPG, outperforms baselines in learning emergent collaborative behaviors and sets the state-of-the-art in decentralized cooperative MARL tasks. Our experiments validate the utility of InfoPG by achieving higher sample efficiency and significantly larger cumulative reward in several complex cooperative multi-agent domains.

Published as a conference paper at ICLR 2022
ITERATED REASONING WITH MUTUAL INFORMATION IN COOPERATIVE AND BYZANTINE DECENTRALIZED TEAMING
Sachin Konan', Esmacil Seraj", Matthew Gombolay Georgia Institute of Technology Atlanta, GA 30332. USA (skonan, eseraj3 eeateggaaeehheeeeeeo edu, matthew. natthhew..emmblayyyoeeeeeeet edu
ABSTRACT
Information sharing is key in building team cognition and enables coordination and cooperation. biigh-performing human teams also benefit from acting strategically with hierarchical levels of iterated communication and rationalizability, meaning a human agent can reason about the actions of their teammates in their decision- making. Yet, the majority of prior work in Multi-Agent Reinforcement Learning (MARL) does not support iterated rationalizability and only encourage inter-agent communication, resulting in a suboptimal equilibrium cooperation strategy. In this work, we show that reformulating agent's policy to be conditional the policies of its neighboring teammates inherently maximizes Mutual Information (MI) lower-bound when optimizing under Policy Gradient (PG). Building on the idea of decision-making under bounded rationality and cognitive hierarchy theory, we show that our modified PG approach not only maximizes local agent rewards but also implicitly reasons about MI between agents without the need for any explicit ad-hoc regularization terms. Our approach, InfoPG, outperforms baselines in learning emergent collaborative behaviors and sets the state-of-the the--art in decentralized cooperative MARL tasks. Our experiments validate the utility InfoPG by achieving higher sample efficiency and significantly larger cumulative reward in several complex cooperative multi-agent domains.
INTRODUCTION
Information sharing is key in building team cogmition, and enables agents to cooperate and successfully achieve shared goals (Salas al. 1992). In addition to communication, individuals in
human teams also benefit from the theory of mind (Frith Frith 2005) and making strategic decisions by recursively reasoning about the actions (strategies) of other human members (Goodie jt al. 2012). Such hierarchical rationalization alongside with communication facilitate meaningful cooperation in human teams (Tokadli & Dorneich (019). Similarly, collaborative Multi-agent Reinforcement Learning (MARL) relies on meaningful cooperation among interacting agents in common environment (Olichock & Amato 2016). Most of the prior works on collaborative MARL are based on the maximum utility theory paradigm which assumes perfectly informed, rational agents (Guan et al., (02I). Nevertheless, even under careful handcrafted or machine learned coordination policies, it is unrealistic and perhaps too strong to assume agents are perfectly rational in their decision- maiiing (Wen al. 20200 Gilovich al. 2002 Simon 1997
Paleja al., (021).
To learn cooperation protocols, prior MARL studies are commonly deployed under Decentralized Partially Observable Markov Decision Processes (Dec-POMDP), which agents interact to maximize a shared discounted reward. More frrentty.fully-deeeeeee fully-decentrallized (F-Dec) MARL was introduced (Zhang cct al., 2018 Yang et al. 2020) to address the credit assignment problem caused by the shared-reward paradigm in conventional Dec-POMDPs (Yang et al. 2020 Sutton 1985). In an F-Dec MARL setting, agents can have varying reward functions corresponding to different tasks (e.g., in a multi-task RL where agent solves multiple related MDP problems) which are only known to the corresponding
"Co-first authors. These authors contributed equally this work.

---

Published as a conference paper at ICLR 2022
agent and the collective goal is to maximize the globally averaged return over all agents. Nevertheless, under an F-Dec setting, agents seek to maximize their own reward, which does not necessarily imply the maximization of the team long-term return since agents do not inherently understand coordination.
Recently, strong empirical evidence has shown that Mutual Information (MI) is a statistic that corre- lates with the degree of collaboration between pairs of agents (Trendafilov et al. 2015). Researchers have shown that information redundancy is minimized among agents by maximizing the joint entropy of agents' decisions, which in turn, improves the overall performance MARL (Malakar al.) 2012). Therefore, recent work in MARL has sought to integrate entropy regulari sgularization terms as means of maximizing MI among interacting agents (Kim al. 2020 Wang et al. 2019 Jaques et al., 2019). The formulaic calculation of MI relies upon the estimation of oction-conditions distributions. In most prior work, agents are equipped with conventional state-conditional policies, and researchers employ techniques, such as variational inference, for estimating and optimizing an action-conditional policy distribution to quantify MI (Wen et al.) 2019 Kim et al.] 2020). However, agents are not explicitly given the ability to reason about their teammates' learn implicitly from sparse rewards or aand-engineered regularization and auxiliary loss terms.
and, instead, have to
In this work, we propose a novel information-theorett fully-distributed cooperative MARL framework, called InfoPG, by reformulating an agent's 's policy to be directly conditional on the policies of its instantaneous neighbors during Policy Gradient (PG) optimization. We study cooperative MARL under the assumption of bounded rational agents and leverage action-conditionall policies into PG objective function accommodate our assumption. By leveraging the k-level reasoning (Ho & Sul (2133) paradigm from cognitive hierarchy theory, we propose cooperative MARL framework in which naive, nonstrategic agents are improved to sophisticated agents that iteratively reason about the rationality of their teammates for decision-making InfoPG implicitly increases MI among agents' k-level cittionnoodiiionall policies to promote cooperativity. To learn collaborative behavior, we build InfoPG on communicative fully-decentralizer structure where agents learn to achieve consensus their actions and maximize their shared utility by communicating with their physical neighbors over a potentially time-varying communication graph. We show the effectiveness of InfoPG across multiple, complex cooperative environments by empirically assessing its performance against several baselines. The primary contributions of our work are as follows:
Contributions
1. We derive InfoPG, an refformation-thhereee PG framework that leverages cognitive hierarchy and action-conditional policies for maximizing MI among agents and maximizing agents' individual rewards. We derive an analytical lower-bond for MI estimated during InfoPG and provide mathematical reasoning underlying InfoPG's performance.
2. We propose a fully-decentrralized graph- based communication and kelevel reasoning struc- ture to enable theory of mind for coordinating agents and maximizing their shared utility.
3. We propose generalized variant of InfoPG and derive MI upper-bound bound to modulate MI among agents depending on cooperativity of agents and environment feedback. We demonstrate the utility of this generalization in solving instance of the Byzantine Generals Problem (BGP), in a fully decentralized setting.
4. We present quantitative results that show InfoPG sets the SOTA performance in learning emergent cooperative behaviors by converging faster and accumulating higher team rewards.
2 RELATED WORK
Cooperative MARL studies can be subdivided into two main lines of research, (1) learning direct com-
munication among agents to promote coordination (Foerster et al.) 2016 Das al. 2018 Sukhbaatar et al. 2016 Kim et al. 2019) and, (2) learning to coordinate without direct communication (Foer- ster et al. 2017 Palmer et al. 2017, Seraj et al., 202Tb). Our work can be categorized under the former. Hicrarchical approaches are also prevalent for learning coordination in MARL (Scraj & Gombolay 2020 Ghavamzadeh & Mahadevan 2004: Amato et al. [2019] Seraj et al. 2021a). We consider MARL problems in which the task in hand is of cooperative nature and agents can directly communicate, when possible. Unlike these studies, however, we improve our interacting agents from coexisting to strategic by enabling the recursive k-leeel reasoning for decision-makin -making.
Researchers have shown that maximizing MI among agents leads to maximizing the joint entropy of agents' decisions, which in turn, improves the overall performance in MARI. (Malakar al.)
2

---

Published as a conference paper at ICLR 2022
Kim et al. 2020). As such, prior work has sought increase MI by introducing auxiliary MI regularization terms to the objective function (Kim et al., [020 Wang et al. 2019 Jaques et al.] 2019). These prior works adopt centralized paradigm, making them less relevant to our F-Dec setting. Model of Other Agents (MOA) was proposed by JJaquss et al. (2019) as a decentralized approach that seeks to locally push the MI lower-bound and promote collaboration among neighboring agents through predicting next-state actions of other agents. In all of the mentioned approaches, the amount of MI maximization objective that should be integrated into the overall policy objective is dictated through a 33 regularization parameter. In our work, however, we reformulate an agent's 'eent's policy to be directly conditional on the policies of its neighbors and therefore, we seek to reason about MI among agents in our PG update without ad-hoc regularization reward shaping.
2012
Among prior work seeking to enable k-level reasoning for MARL,, Wen et al. 2019) presented Probabilistic Recursive Reasoning (PR2), an opponent modeling approach to decentralized MARL in which agents create a variational estimate of their opponents' level h actions and optimize a joint Q-function to learn cooperative policies without direct communication. Wen al. (2020) later extended the PR2 algorithm for generalized recursive depth of reasoning. In InfoPG, we establish the inherent connection between k-level reasoning and MI, link that has not been explored in prior work. Moreover, we bypass the need for modeling other agents through direct communication and k-level action-conditional policies, and giving InfoPG agents the ability to recursively reason about their teammates" actions through received messages and with any arbitrary rationalization depths.
PRELIMINARIES
Problem Formulation - We formulate our setup as a Multi-Agent Fully Dec-POMDP (MAF-Dec- POMDP), represented by an 8-tuple [[ .,, A, Ω2 kex, 7). N is the set of all interacting agents in the environment in which index i represents the index of an agent. G. = (N, & time-vane varrii, undirected communication graph in which agents i,j E N are vertices and E, S ((1 :i,j N, * j} is the edge set. The two agents and j can only share information at time I if (1, E & State space S is a discrete set of joint states, A represents the action space, f2 is the observation space, and 7 E [0, 1) is the temporal discount factor for each unit of time.
At each step, i, an agent, i, receives a partial observation, of E 22 takes an action, of E A, and receives an immediate individual reward, r/ E {RR) Taking joint actions, in the joint states, 5, leads to changing the joint states to 8' E S, according to the state transition probabilities, P (3'18, a). Our model is fully decentralized since agents take actions locally and receive individual rewards for their actions according to their own reward function. Moreover, each agent is also equipped with a local optimizer update its individual policy through its local reward feedback. Accordingly, can reasonably assume that agents' choices of actions are conditionally independent given the current joint states (Zhang et al. 2018). In other words, if S x A [0, 1] is the joint state-conditional policy, we assume that π ((.)) = IL (a") 5)). Note that
are allowed to facilitate local inter-agent communication [haang et al. 2018 Olihhokk & Amato 2016 Melo al. 201T).
Policy Gradient (PG) and Actor-Critic (AC) Methods The policy gradient methods target at modeling and optimizing the policy n' directly by parametrizing the policy, T/ (a]lss)) Actor- Critic (AC) is policy gradient method in which the goal is to maximize the objective by applying gradient ascent and directly adjusting the parameters of policy, Th. through an actor network. The actor, updates the policy distribution in the direction suggested by critic, which estimates the action-value function (",,,, (Tesauro 1995). By the policy gradient theorem (Sutton & Barto 2018), the gradient by which the objective in AC, (()), is maximized can be shown as (5,, a.)]. where of and of are agent i's action and observation. (oJ(O) = Ex [Vo T (
Mutual Information (MI) - MI is measure of the reduction in entropy of probability distribution, X, given another probability distribution Y, where H(X) denotes the entropy of X and ( Y) denotes the entropy of the conditional distribution of X given Y (Kraskov et al. 2004 Poole et al. 2019, By expanding the Shannon entropy of X and X|Y, we can compute the MI as in Eq.
PX Px|Y=
I(X:)) = H(X) - H(XIV) = EeV (v) Σ (x) log
Px (x)
WEY
ZEX
In our work, X and Y are distributions over actions given a specific state, for two interacting agents. In an arbitrary Markov game with two agents and j and with policies n. and Ty. if т. gains MI by viewing xy, then agent will make a more informed decision about its sampled action and vice versa.
3

---

Published as a conference paper at ICLR 2022
Encoding
K 1 Communication
K> Communication
Agent
s'
Rane
A(O
(A(33)
c.oo
Rcom
aa
Agent j
sl
a
a1i(1
IT com
TT com
com
Figure I: An instance of the information flow in k-level decision hierarchy between two agents and for calculating their level-k strategies. Level-zero actions (c.g., a a0)) represent the naive non-strategic actions.
4 MUTUAL INFORMATION MAXIMIZING POLICY GRADIENT
In this section, we first present an algorithmic overview of the InfoPG framework and then introduce the InfoPG objective by covering the logistics of building an iterated k-level decision making strategy for agents with bounded rationality. We then explore the relation of InfoPG with MI and derive an analytical lower-bound on the MI between the action-conditional policies of interacting agents.
4.1 ALGORITHMIC OVERVIEW
Consider an MAF-Dec-PONAA introduced in Section B with N agents where each agent is equipped with an encoding and a communicative policy (see Fig. D. At the beginning of a new rollout, each agent receives state observation from the environment and produces an initial action (i.e., guess action) using its encoding policy. Each agent has a neighborhood of agents can communicate with, shown with j A where [ is the number of agent i's physical neighbors (i.e., within close proximity). Next, depending on the level of k in the decision hierarchy, agents communicate their action guesses (high-dimensional latent distributions) with their neighbors k times and update their action guess iteratively using their communicative policy. The level-k action is then executed by all agents and a local reward given to each agent separately. This process continues until either the environment is solved successfully, or some maximum number of cycles has been attained. For each timestep, I, of the policy rollout and for each agent i, the gradient of the log probability computed, scaled by the instantancous advantage, A}. and the encoding and communicative policies updated. This process repeats until convergence of the cumulative discounted rewards across all agents. Please refer Appendix, Section I. for pseudocode and details of our training and execution procedures.
4.2 DEEP REASONING: DECISION-MAKING UNDER LELELL RATIONALIZATION
We leverage from cognitive hierarchy theory (Camerer et al. 2004) and strategic game theory (yyr son 2013), wherein each agent has k-levels of conceptual ization of the actions its neighbors might take under bounded rationality. k-level reasoning assumes that agents strategic games are not fully rational and therefore, through hierarchies of iterated rationalizability. each agent bases its decisions on its predictions about the likely actions of other agents (Ho & Sul 2013). According to k-level theory, strategic agents can be categorized by the depth of their strategic thought (Nagel) 1995). For example, consider the two agent case shown in Fig. 1 with k = 2. At = agent makes decisions based off its own observed state, and a guess of what agent j will do (Agent i will assume agent is naive and non-strategic). A more sophisticated agent i with a strategy of level A = 2 however, makes decisions based off the rationalization that agent j has a level-one guess of i's strategy. Inductively, this line of reasoning can be extended to any k. Notice that the conditioning of agent i's policy on agent j's perceived actions an action-conde condinoonniiionall distribution. In InfoPG, we give agents the ability to communicate with their latent guess-action action distributions in & iterated reasoning steps and rationalize their action decisions at level i to best respond to their teammates' level
actions.
In the following, we represent the level of rationality for an agent by the superscript (k) where k E N. Denoting a*((k) as the level-k: policy of agent j, it can be shown that under the k-level reasoning, agent i's policy at level A + 1, (k+(k)),, is preciscly the best response of agent i to agent j's policy TJ.(A) (Guan et al. 2021 }. In other words, πt (+((k+1) E BestResponse(rsi0)) In theory, this process can iteratively proceed until we obtain ri((k+2) = (8), which corresponds to reaching the equilibrium strategies. In practice, however, for scenarios with many collaborating agents, the
4

---

Published as a conference paper at ICLR 2022
level of le is usually set to reasonably small number for computational efficiency; since, in order to calculate the policy xf.(k) agent i must calculate not only its own policy at level k, but also all policies of all its neighbors for all 21,2,3... ... l 1} at each time-step I.
4.3 INFOPG ORJECTIVE
Our approach, InfoPG, equips each agent with detiooncoonitionall policy that performs actions based on an iterated k-level rationalization of its immediate neighbors' actions. This process can be graphically described presented in Figure I in which the information flow in k-level reasoning between two agents i and j is shown. Note that in practice, any number of agents can be applied. Considering agent as the current agent, we represent i's decision-mann maaonn policy as Teot = | c.om] in which T (a [ is the state-conditional policy that maps i's observed states actions. T Trom (a) |a, (1) a3
is the action-condiitonal policy that maps agent i's action at level (A: -1-1 along with the actions of i's neighbors (in this case agent j) at level k - 1, to an action for agent
the (k+)-th level of decision hierarchy, a, (.(()) Therefore, pursuant
the general PG objective, we define the basic form of our modified information baaeed objective, as in Eq. 2 where A is the set of i's immediate neighbors communication graph at time and G, is the return.
latoPG (0) = Briio Giloi a V
1.(k-1) ()(--1,, Σ Ve Ve Volog(Tior(a 6,08) [a of jEat
8.(0)
(.(0) of))
(2)
Eq. 2 describes the form of InfoPG's objective function. Depending on the use case, we can replace the return, G₁, with action- values, Q/ shown in Eq. 3 and present the InfoPG Monte-Carlo PG method. We can also replace the returns with the advantage function, Ad, as shown in Eq. 4 and present the AC variant of the InfoPG objective (Sutton Barto 2018).
Go at) Qi(oi, at) (o a.) at) Qi(ol, - (o.)
Qi(oi,
(3)
(4)
Leveraging Eq. Bq and we present two variants of the InfoPG objective. The first variant is the MI maximizing PG objective, which utilizes Eq. [ The non non-negative action-value condition in Eq. implies non-negative rewards from the environment, a common reward paradigm utilized in prior work (Fellows et al. [219 Liu et al. 2020 Kostrikov et al. 2018). By applying this condition, InfoPG only moves in the direction of maximizing the MI between cooperating agents (see Theorem 2}. We refer to the second variant of our InfoPG objective shown in Eq. 4as Advantage InfoPG (Adv. InfoPG), in which we relax the non-negative rewards condition. Adv. InfoPG modulates the MI among agents depending on cooperativity of agents and environment feedback (see Theorem 3).
4.4 BAYESIAN EXPANSION OF THE POLICY
The action- cetion-conditional policy conditions an agent's action at the k-th level of the decision hicrarchy on the actions of other agents at level k: - 1; however, to relate our k-level formulation to MI, we seek to represent an agent's action at particular level l: to be dependent on the actions of other agents at same level k. We present Theorem to introduce the gradient term in the InfoPG objective Eq. P which relates level-A actions of the cooperating agents in their respective decision hierarchies. Please refer to the Appendix, Section A.3 a detailed proof of Theorem]] T
Theorem 1. The gradient of the log probability's 's level-k action-distribution in the InfoPG objective (Eq, 2 for an agent, i, with neighbors j E D; and policy Tiot that takes the Maximum a Posteriori
(MAP) action a, s.lk)
can be calculated iteratively for each level k of rationalization via Eq. 5
log(s)a((a (.(k) MAP a.
1100-1) (.(0--1) ......)))) V Vogg( (a(((k) -MPP 2 MAP))
(5)
4.5 INFOPG AND MUTUAL INFORMATION LOWER- -OUUD
())) is directly proportional to V log( (a, (.(k) (. (A)))) from Eq. 5 we can show that the gradient of our communicative policy implicitly changes MI. Since MI instead derive a lower-bound for MI which is dependent on the action-ce iition-conditional policy of an agent. We show that increasing the probability of taking an action from the action-conditional policy will increase the derived lower-bound, and consequently, the MI.
Using the fact that V (lg(((jod (T (c).
empirically hard to estimate,
5

---

Published as a conference paper at ICLR 2022
Theorem 2. Assuming the actions (az ( and 5:0k) to be the Maximum a Posteriori (MAP) actions, the lower-bound to MI, T(0 (1; between any pair of agents and j that exist in the communication graph ge can be calculated w.t.f to agent i's communicative policy as shown in Eq. 6
de
4.(0) (0.000aa (.00) log(From(()) 2.(K) (ab la
(2(0))) S ((;
Tcom (a)
(6)
Proof - Without loss of generality, we consider two agents i.j E N with condiinnoniii policies (aalaa²)) and T² (aallaa) (note that the time, t, and the rationalization level, (k:), indices are removed for notational brevity). We refer to the marginalizations of i's and j's action-conditional policies as priors which can be denoted as p(a') = Eas E.A x ra(aaaa)) and p(a') = Enred X 7 (a²). We assume uniformity of the priors, as done previously by Prasad 2015). such that p(a') = p(a') l
I
where |A] is the action-space dimension. For a detailed discussion the validity of the uniformity of priors assumption, please refer to the Appendix, (ection[A.G] Since MI is a marginalization across all actions in the action-space, lower-bound exists partieular amazr which is the MAP action. we derive:
As such, starting from the basic definition of MI in [
(x'(a(aa)) p(at)
I(t:)) Epaa') Σ (a'(alaa)) (a') log
Σ
Σ a'EA
7 (aaaaaa)) la') log((A)('(a'aaa)) (7)
a'EA 2 |A|T' [Alar'a'mmzzl' (log (Tr(a lat)) + log (LA1))
aA
aiEd
2 x (a (ai log (T (cimarlaa)
(8)
We now seek to relate the last term in Eq. to the gradient term V Vlog(Tt (og(T)om (a) (a):(k) at (.(0)) and variation of MI. By monotonicity of log, maximizing loy(T' (a lad) is equivalent to maximizing the n' T'(atazzl
|a²) term. Therefore, according to Theorem 2 and Eq. 8 the gradient updates will raise our lower-bound, which will maximize the MI. Since the sign of environment rewards and therefore, the sign of Qr(Or, ac) in Eq. i is strictly non-negative, the gradient ascent updates will always move log(rie ( (a, (.()k)
(a, a ( either up not-at-all, which will have a proportional effect the MI given the bower-bound. Note that we leveraged the non-negative reward condition so that the rationalization of a (.(k) given (.(()) is only non-negatively reinforced. As such, if agent i's action-conditional policy on agent j's action does not obtain a positive reward from the environment, the lower-bound of MI stays constant, and thus does MI. Conversely, if positive reward is received by the agent, then the lower-bound of MI will strictly increase, leading to lowering the conditional entropy for taking the action that yielded the positive feedback from the environment.
4.6 ADVANTAGE INFOPG AND THE BYZANTINE GENERALS PROBLEM
While continually maximizing MI among agents is desired for improving the degree of coordination, under some particular collaborative MARL scenarios such MI maximization may be detrimental. We specifically discuss such scenarios in the context of Byzantine Generals Problem (BGP). The BGP describes decision-making scenario in which involved agents must achieve an optimal collaborative strategy, but where at least one agent is corrupt and disseminates false information or is otherwise unreliable (Lamport et al. 2019). BGP scenarios are highly applicable to cooperative MARL problems where there exists an untrainable fraudulent agent with a bad policy (c.g., random) in the team. Coordinating actions with such fraudulent agent in collaborative MARL setting can be detrimental. We note that BGPs are particularly challenging to solve in the fully decentralized settings (Peng al. |021 Allen-Zhu et al. 2020).
Here, we elaborate on our Adv. InfoPG variant introduced in Eq. 4 Hnd show its utility for intelligently modulating MI depending on the cooperativity of agents. Intuitively, the advantage function evaluates how much better it is to take a specific action compared to the average, general action at the given state. Without the non-negative reward condition InfoPG, the Adv. InfoPG objective in Eq. 4 does not always maximize the MI locally, but, instead, benefits from both positive and negative experiences as measured by the advantage function to increase the MI in the long run. Although instantaneous experiences may result in a negative advantage, A;. and reducing the MI lower-bound in Eq. 6 we show that Adv. InfoPG in fact regularizes an MI upper-bound, making it suitable for BGP scenarios while also having the benefit of learning from larger number of samples. In Adv. InfoPG we equip each agent with an action-condee conditional policy and show that under leleeel reasoning, the tight bounds of MI between agents is regularized (shifted up and down) depending on the sign of the received advantage. We note that despite this local MI regularization, in the long run we expect the MI bounds to increase since policy gradient seeks to maximize local advantages during gradient ascent.

---

Published as a conference paper at ICLR 2022
Upper-Bound of MI Here, we derive MI upper-bound dependent on the policy of an agent and show that the gradient updates in Adv. InfoPG have a proportional effect on this upper-bound We show that under k-level rationalization, the tight bound of MI between agents is regularized (shifted up or down) depending on the sign of the received advantage value, Aj.
the upper-bound to MI, T between agents and j w.r. agent i's level-k action-conditione policy can be calculated as in Eg.
Theorem 3. Assuming the same preliminaries as in Theorem 2
(1: S log( (A) + 2 log (a;
(,00) at (200)))
Proof - We start from the definition of conditional entropy. The conditional entropy is an expectation across all a² and considering the fact that the log(-) a convex function, Jensen's 's inequality (Ruel
& Ayres 1999) can be applied to establish an upper-hound on conditional entropy. We derive:
H(*(x²)=- = Σ (aalaa)) log(T (a'l = Σ
x (a'(aa))( (a'r'aaa''" (a'la')))
(10)
E'A
a'EA
Jansen's inequality
H( H(x'TT2) - llog( Σ x xaaaaa²))
(11)
a'EA
Now, we leverage the basic MI definition in Eq. 1 We note that H(((a)) has a constant value of log((A))) given the uniform prior assumption. Accordingly, plugging in the bound in Eq. [I and evaluating at the MAP action results in an upper-bound for MI, as shown below.
[(i:j) = H(p(a')) - H (I'(>²) -H (sr Imr) + log(lAA) S log( Σ aaaa"'a")")+ log(1A4)
(12)
a'EA
$log (IA)r ( (a²)) + ((4) < 2 [og((AA|) + 2 log (T (amazlaa²)
(13)
depending on the sign of Ai, the gradient ascent (.()) (1()) which will have a proportional regulatory effect either increases or decreases log(T coom (az
Considering the Adv. InfoPG objective in Eq.
on the MI given our bounds in Eq. 6 and 9 Specifically, when agent receives negative advantage
from the environment, it means agent i's reasoning of (.(k) given (.(k) resulted in negative outcome. Therefore, to reduce agent j's negative influence, our gradient updates in Eq. 4 will decrease the MI upper-bound between i and j so that the conditional entropy at level l: is increased. This bears similarity to Soft actor-critic (Haarnoja et al.) 2018), where regularization with entropy allows agents to explore more actions. As such, during Adv. InfoPG updates, the MI constraint becomes adaptive to instantaneous advantage feedback. Such property can be effective in BGP scenarios reduce the negative effect of misleading information received from a fraudulent agent.
5 EMPIRICAL EVALUATION
Evaluation Environments - We empirically validate the utility of InfoPG against several baselines in
four cooperative MARL domains that require high degrees of coordination and learning collaborative
behaviors. Our testing environments include: (1) Cooperative Pong (Co-op Pong) (Terry et al.) (2020), (2) Pistonball (Terry et al.] 2020), (3) Multiwalker (Gupta et al. 2017 Terry et al. (020) and, (4) StarCraft II (Vinyals et al. 2017), i.e., the 3M (three marines vs. three marines) challenge. We modified the reward scheme in all four domains to be individualistic such that agents only receive
a local reward feedback as per our MAF-Dec-POMMD formulation in Section 3 For environment
descriptions and details, please refer to the Appendix, Section A.8
Baselines- We benchmark our approach (both InfoPG in Eq. 3 and Adv. InfoPG in Eq. against four fully-decemtrallzee baselines: (1) Non-communicative A2C (NC-A2C) (Sutton & Barto 2018
(2) Consensus Update (CU) (Zhang et al., 2018). (3) Model of Agents (MOA) (Jaques et al. 2019 and, (4) Probabilistic Recursive Reasoning (PR2) (Wen et al. 2019). In the NC-A2C, each agent controlled via an individualized actor-critic network without communication. The CU approach shares the graph-based communication among agents with InfoPG but lacks the k-level reasoning in InfoPG's architecture. Thus, the CU baseline is communicative and non non-rational MOA, proposed by Daques et al. (2019), is a decentralized cooperative MARL method in which agents benefit from action-conditional policies and an MI regularizer dependent on the KL-Divergence between an agent's s prediction of its neighbors' actions and their true actions. PR2, proposed by Wen et al. (2019) is an opponent modeling approach to decentralized MARL in which agents create a variational estimate of their opponents' level l I actions and optimize a joint Q-function learn cooperative policies through kllevel reasoning without direct communication.
7

---

Published as a conference paper at ICLR 2022
info@g Well) (Ours)
InfoPG (K-2) (Ours) EU [chungg us al. 2018)
InfoPG (K-3) (Ours)
Adv. IntoPG [K=1] t0urg) PR2-AC (Wen et ei., 2019)
NI LB/UB
NC-A2C (Sutton & Darto, 2010)
MDA (Jeqar et 2019)
Co-op Pong
PistonBall
Multiwalker
StarCraft (3M)
Cum. Team Reward
0.4
0.2
-20
-0.2
-30
-0.4
-50
1000 Episodes
2000
3000 4000
600 Episodes
400
800
1000
-60
200
400
600
800 1000
200 400 600 800 1000
Episades
Episodes
Co op Pong
PistonBall
Multiwalker
StarCraft (3M)
Mutual Information
3.0
3.0
2.5
2.5
2.0
2.0
0.5
2
1.0
0.5
0.5
00.5
1
0.0
0.0
2000
4000
400
Episodes
Episodes
Episodes
Episodes
Figure 2: (Top Row) Team rewards obtained across episodes as training proceeds. The shaded regions represent standard error. Our Ady. InfoPG continually outperforms all baselines across all domains and in both training and testing (see Table (Bottom Row) The MI ablation study results, comparing the MI variations between InfoPG and MOA (MI-based bascline) where InfoPG demonstrates higher final average MI estimate across all domains. The shaded blue region represents the area between InfoPG's lower and upper bounds MI.
6 RESULTS, ABLATION STUDIES, AND DISCUSSION
In this section, we assess the performance and efficiency of our frameworks in the four introduced domains and against several recent, delly-decentralized cooperative MARL approaches. Following an analysis of performance under k-level reasoning and an MI ablation study, we present a case-study, namely the fraudulent agent experiment, investigate the utility of our MI-regularizing InfoPG variant (i.e. Adv. InfoPG in Eq. against MI-maximizing baselines, such as MOA (Jaques et al. 2019) and InfoPG, in BGP scenarios. We provide further ablation studies, such as level-k policy interpretation for InfoPG and a scalability analysis the Appendix, Section A.7
Baseline Comparison The top row in Fig. 2 depicts the team rewards obtained by each method across episodes as training proceeds. In all four domains, both InfoPG and Adv. InfoPG demonstrate sample-efficiency by converging faster than the baselines and achieving higher cumulative rewards. Table I presents the mean (#standard error) cumulative team rewards and steps taken by agents win the game by each method at convergence. Table D shows that InfoPG and Adv. InfoPG set the state-of-the-art for learning challenging emergent cooperative behaviors in both discrete and continuous domains. Note that, while Pistonball fewer number of taken steps means better performance, in Co-op Pong and Multiwalker more steps shows a superior performance.
The bottom row Fig. 2 shows our MI study results comparing the MI variations between InfoPG and MOA (the MI-based baseline). The MI for InfoPG estimated as the average between lower and upper bounds defined in Eqs. [ InfoPG demonstrates a higher final average MI estimate across all domains. Note the concurrency of InfoPG's increase MI estimates (bottom row) and agents' performance improvements (Fig. 2 top row). This concurrency supports our claim that our proposed policy gradient, InfoPG, increases MI among agents which results in learning emergent collaborative policies and behavior.
Mutual Information Variation Analysis
Gnd and g As depicted,
We evaluate the performance of our method for deeper levels of reasoning E {2.3) 3) in Co-op Pong. Pistonball and Multiwalker domains. The training results presented in Fig. 2] As discussed in Section 4.2 in the smaller domain with fewer collaborating agents, the Co-op Pong, agents reach the equilibrium cooperation strategy (i.e., ++)+++2 = π (k)) even with one step reasoning, and increasing the level of & does not significantly change the performance. However, in the more complex domains with more agents, Pistonball and Multiwalker, as the level of rationalization goes deeper in InfoPG (i.e., = 2 and k 3), agents can coordinate their actions better and improve the overall performance.
Deep Reasoning for Decision Making: Evaluating L-Level InfoPG
8

---

Published as a conference paper at ICLR 2022
Table Reported results Mean (Standard Error) from 100 testing trials. For all tests, the final training policy convergence used for each method and for InfoPG and Adv. InfoPG, the best level & chosen.
InfoPG
Adv.
InfoPG
MOA
CU
NC-A2C
PR2-AC
Domain
R
#Steps
R
#Steps
R
#Steps
R
#Steps
R.
#Steps
R.
#Steps
0.127
202.9
0.25
212.9
-0.3
58.2
0.13
152.0
0.04
102.925
-0.84
36,8
Co-op Pong
(0.00)
(1.35)
(0.00)
(1.24)
(0.00)
(0.32)
(0.00)
(0.96)
(0.00)
(0.93)
(0.00)
(0.34)
7.47
17.44
7.33
28.31
4.10
91.66
1.06
136.3
0.89
138.3
1.90
140.4
Pistonball
(0.02) (0.29)
(0.02)
(0.43)
(0.03)
(0.76)
(0,04)
(0.83)
(0.04)
(0.83)
(0.02)
(0.68)
3.56
474.2
11.81
500.0
0.66
489.3
-1.7
490.2
-66
80.75
-84
94.17
Multiwalker
(0.20)
(1.39)
(0.11) (0.80)
(0.15)
(1.09)
(0.26)
(1.30)
(0.18)
(0.20)
(0.37)
(1.40)
4,40
30.79
3.73
44.5
2.78
27.7
0.24
58.72
0.00
60.0
0.64
27.4
StarCraft
(0.01) (0.05)
(0.02)
(0.13)
(0.02) (0.07)
(0.00)
(0.06)
(0.00)
(0.00)
(0.00)
(0.08)
The Fraudulent Agent Experiment: Regularising MI To assess our Adv. InfoPG's (Eq. regulatory effect based on agents' cooperativity, perform experiment, demonstrated in Fig. which is performed in the Pistonball domain and is intended to simulate an instance of the BGP in which the middle piston is equipped with a fully random policy throughout the training (i.e., the Byzantine piston is not controllable by any InfoPG agent). Maximizing the MI with this fraudulent agent is clearly not desirable and doing such will deteriorate the learning performance.
Fig. 3b presents the fraudulent agent experiment training results for Adv. InfoPG, InfoPG and MOA. As shown and comparing with Fig. [ existence of fraudulent agent significantly deteriorates the learning performance in MOA and InfoPG as these approaches always seek to maximize the MI among agents. This is while InfoPG still outperforms MOA since by only using strictly non- negative rewards, the coordination in InfoPG is only positively reinforced, meaning that InfoPG only increases MI when the reward feedback positive. Adv. InfoPG shows the most robust performance compared to InfoPG and MOA. Adv. InfoPG modulates the MI depending the observed short-term coordination performance. As discussed in Section [4.6] if the advantage is negative, the gradient ascent in Adv. InfoPG will decreases the MI upper-bound between agents, leading to increasing the conditional entropy and taking more exploratory (i.e., less coordinated) actions.
fraudulent agent with rundom policy
Cum. leam Reward
Inforn (c=1] [Duns)
Adv. Enlonu (um3) (Qura) MDA [34]
(9)
(8)
(4)
13)
(2)
(numbers represent piston agent indicas)
200
400
Episodes
600
800
1000
(a) The Fraudulent Agent Experiment: Scenario
(b) The Fraudulent Agent Experiment: Result
Figure 3: The fraudulent agent experiment scenario (Fig. 3a and training results (Fig. 3b in the Pistonbail
domain, comparing the team reward performance for Adv. InfoPG (Eq.E InfoPG (Eq and MOA.
Limitations and Future Work Usefuu MI between agents becomes hard capture in cases, such as Co-op Pong domain, where an agent's 's action influences its neighbors with some delay. Moreover, MI maximization by applying the strictly non non-negative reward condition in InfoPG objective (Eq. comes at the cost of zeroing out negative experiences which may have an impact on sample-efii efficienff
7 CONCLUSION
We leverage iterated k-level reasoning from cognitive hierarchy theory and present collaborative, fully- delenteecnta MARL framework which explicitly maximizes MI among cooperating agents by equipping each agent with an action-conditional policy and facilitating iterated inter-agent communi- cation for hierarchical rationalizability of action-decisions. We analytically show that the design of our MI-based PG method, increases an MI lower- lower-bound, which coincides with improved cooperativity among agents. We empirically show InfoPG's superior performance against various baselines in learning cooperative policies. Finally, we demonstrate that InfoPG's regulatory effect on MI makes Bysiitnne-resilien and capable of solving BGPs in fully-decentrallized settings.

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGMENTS
This work was sponsored by the Office of Naval Research (ONR) under grant N00014-19-1-209 and the Naval Research Lab (NRL) under the grant N00173-20-1-G009,
ETHICAL STATEMENT
Our experiments show that theory mind and cognitive hierarchy theory can be enabled for teams of cooperating robots to assist strategic reasoning. We note that our research could be applied for good or otherwise, particularly in an adversarial setting. Nonetheless, we believe democratizing this knowledge is for the benefit of society.
REPRODUCIBILITY STATEMENT
We have taken several steps to ensure the reproducibility of our empirical results: we submitted, as a supplementary material, our source code for training and testing InfoPG and all the four baselines in all four domains. The source code is accompanied with a README with detailed instructions for running each file. We also publicized our source code in public repository, available online at whttps::/ //ttps::/gitei gigthub..... com/ CORE Robotics ics Lab/InfoFP Additionally, we have provided the details of our implementations for training and execution well as the full hyperparameter lists for all methods, baselines, and experiments in the Appendix, Section A.9 For our theoretical results, we provide explanations of all assumptions made, including the uniformity of priors assumption in Appendix, Section A.6 and the assumptions made for convergence proof in Appendix, Section A.44 Finally, complete proof of our introduced Theorems and 3, as well as InfoPG's convergence proof and the full proof of Theorem 1, are provided in Sections 4.6 and, Appendix, Sections A.4 A.5 respectively.
REFERENCES
Zeyuan Allen-Zhu, Faeze Ebrahimianghazani, Jerry Li, and Dan Alistarh. Byzantine-resilien non- convex stochastic gradient descent. In International Conference on Learning Representations, 2020.
Christopher Amato, George Konidaris, Leslie P Kaelbling, and Jonathan P How. Modeling and planning with macro-actions in decentralized pomdps. Journal of Artificial Intelligence Research, 64:817-859, 2019.
Yoshua Bengio, Jérôme Louradour, Ronan Collobert, and Jason Weston. Curriculum learning. In Proceedings of the 26th annual international conference machine learning, pp. 41-48, 2009.
Shalabh Bhatnagar, Richard S Sutton, Mohammad Ghavamzadeh, and Mark Lee. Natural actor-critic algorithms. Automatica, 45(11))2471-2433 2009.
Vivek S Borkar. Stochastic approximation with time scales. Systems & Control Letters, 29(5): 291-294, 1997.
Colin Camerer, Tuck-Hua Ho, and Juin-Kuan Chong. cognitive hierarchy model of games. The Quarterly Journal of Economics, 119(3):811889) 2004.
Abhishek Das, Théophile Gervet, Joshua Romoff, Dhruv Batra, Devi Parikh, Michael Rabbat, and Joelle Pineau. Tarmac: Targeted multi-agent communication. arXiv,, 2018.
Matthew Fellows. Anuj Mahajan, Tim GJ Rudner, and Shimon Whiteson. Virel: A variational inference framework for reinforcement learning. Advances in Neural Information Processing Systems, 32:7122 12.7122-7736, 2019.
Jakob Foerster, Ioannis Alexandros Assael, Nando De Freitas, and Shimon Whiteson. Learning to communicate with deep multi-agent reinforcement learning. In (NeurIPS), pp. 2137-2145, 2016.
10

---

Published as a conference paper at ICLR 2022
Jakob Foerster, Nantas Nardelli, Gregory Farquhar, Triantafyllos Afouras, Philip HS Torr, Pushmeet Kohli, and Shimon Whiteson. Stabilising experience replay for deep multi-agent reinforcement learning. In (ICML), pp. 1146-1155. PMLR, 2017.
Chris Frith and Uta Frith. Theory of mind. Current biology, 15(17):6644 R647))66444---,,, 2005.
Samuel J Gershman, Eric J Horvitz, and Joshua B Tenenbaum. Computational rationality: A converging paradigm for intelligence in brains, minds, and machines. Science, 349(6245):273-27, 2015.
Mohammad Ghavamzadeh and Sridhar Mahadevan. Learning to communicate and act using hierar- chical reinforcement learning. Computer Science Department Faculty Publication Series, pp. 172, 2004.
Thomas Gilovich, Dale Griffin, and Daniel Kahneman. Heuristics and biases: The psychology of intuitive judgment. Cambridge university press, 2002.
Adam Goodie, Prashant Doshi, and Diana L Young. Levels of theory-of-mint reasoning in competitive games. Journal of Behavioral Decision Making, 25(1):95-100) 2012.
Yue Guan, Dipankar Maity, Christopher M Kroninger, and Panagiotis Tsiotras. Bounded-rational pursuit-cvasion games. In 2021 American Control Conference (ACC), pp. 3216-3221. IEEE, 2021.
Jayesh K Gupta, Maxim Egorov, and Mykel Kochenderfer. Cooperative multi-agent control using deep reinforcement learning. In International Conference on Autonomous Agents and Multiagent Systems, pp. 63683. Springer, 2017.
Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with stochastic actor. In (ICML), pp. 1861-1870. PMLR, 2018.
Teck-Hua Ho and Xuanming Su. dynamic level-k model in sequential games. Management Science, 59(2):452 469, 2013.
Natasha Jaques, Angeliki Lazaridou, Edward Hughes, Caglar Gulcehre, Pedro A. Ortega, DJ Strouse, Joel Z. Leibo, and Nando Freitas. Social influence as intrinsic motivation for multi-agent deep reinforcement learning, 2019.
Daewoo Kim, Sangwoo Moon, David Hostallero, Wan Ju Kang, Taeyoung Lee, Kyunghwan Son, and Yung Yi. Learning to schedule communication in multi-agent reinforcement learning. arXiv, 2019.
Woojun Kim, Whiyoung Jung, Myungsik Cho, and Youngchul Sung. A maximum mutual information framework for multi-agent reinforcement learning. arXiv preprint 2rXiv:2006.02733 2020.
Ilya Kostrikov, Kumar Krishna Agrawal, Debidatta Dwibedi, Sergey Levine, and Jonathan Tompson. Discriminator-actor--tiii Addressing sample inefficiency and reward bias in adversarial imitation learning. In International Conference Learning Representations, 2018.
Alexander Kraskov, Harald Stögbauer, and Peter Grassberger. Estimating mutual information.
Physical review E, 69(6))066133 2004.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep con- volutional neural networks. Advances in neural information processing systems, 25:1097-1105, 2012.
Leslic Lamport, Robert Shostak, and Marshall Pease. The byzantine generals problem. In Concur- rency: the Works of Leslie Lamport, pp. 203-226 2019.
Yong Liu, Weixun Wang, Yujing Hu, Jianye Hao, Xingguo Chen, and Yang Gao. Multi-agent game abstraction via graph attention neural network. Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 7211-7218 2020.
NK Malakar, KH Knuth, and DJ Lary. Maximum joint entropy and information- collaboration of automated learning machines. In AIP Conference Proceedings 31st, volume 1443, pp. 230-237. American Institute of Physics, 2012.
11

---

Published as a conference paper at ICLR 2022
Francisco S Melo, Matthiss TJ Spaan, and Stefan J Witwicki. Querypomdp: Pomdp- based commu- nication multiagent systems. In European Workshop on Multi-Agent Systems, pp. 189-204. Springer, 2011.
Roger B Myerson. Came theory. Harvard university press, 2013.
Rosemarie Nagel. Unraveling in guessing games: An experimental study. The American Economic Review, 85(5):3313-135) 1326, 1995.
Frans A Oliehoek and Christopher Amato, concise introduction to decentralized POMDPs. Springer, 2016.
Rohan Paleja, Muyleng Ghuy, Nadun Ranawaka Arachchige, Reed Jensen, and Matthew Gombolay. The utility of explainable ai ad hoe human-machine teaming. Advances in Neural Information Processing Systems, 34, 2021.
Gregory Palmer, Karl Tuyls, Daan Bloembergen, and Rahul Savani. Lenient multi-agent deep reinforcement learning. arXiv, 2017.
Jie Peng. Weiyu Li, and Qing Ling. Byzantine-robust decentralized stochastic optimization static and time-varying networks. Signal Processing. 183:108020, 2021.
Ben Poole, Sherjil Ozair, Aaron van den Oord, Alexander A. Alemi, and George Tucker. On variational bounds mutual information, 2019.
Sudhakar Prasad. Bayesian error-based sequences of statistical information bounds. IEEE Transac- tions on Information theory, 61(9):5052- 5062, 2015.
Jonathan J Ruel and Matthew Ayres. Jensen's ' inequality predicts effects of environmental variation. Trends in Ecology & Evolution, 14(9):361-36,, 1999.
E. Salas, Dickinson, Sharolyn A. Converse, and S. Tannenbaum. Toward an understanding of team performance and training. 1992.
Esmaeil Seraj and Matthew Gombolay. Coordinated control of uavs for human-centered active sensing wildfires. In 2020 American Control Conference (ACC), pp. 1845-1852. IEEE, 2020.
Esmaeil Seraj, Andrew Silva, and Matthew Gombolay. Safe coordination of human-robot firefighting teams. arXiv preprint arXiv: N0.3v:9903300000 1903.0687,7 2019.
Esmaeil Seraj, Xiyang Wu, and Matthew Gombolay. FireCommander: An Interactive, Probabilistic Mulli-agent Environment for Joint Perception-Action Taasks-Presentation Slides. PhD thesis, Georgia Institute of Technology, USA, 2020.
Esmaeil Seraj, Letian Chen, and Matthew C Gombolay. A hierarchical coordination framework for joint perception action tasks in composite robot teams. IEEE Transactions on Robotics, 202
Esmaeil Seraj, Zheyuan Wang, Rohan Paleja, Matthew Sklar, Anirudh Patel, and Matthew Gombolay, Heterogeneous graph attention networks for learning diverse communication. arXiv preprint arXiv:2108.09568, 2021b.
Herbert Alexander Simon. Models of bounded rationality: Empirically grounded economic reason, volume 3. MIT press, 1997.
Sainbayar Sukhbaatar, Rob Fergus, et al. Learning multiagent communication with backpropagation. In (NeurIPS), pp. 2244 2252, 2016.
Richard S Sutton. Temporal credit assignment in reinforcement learning. 1985.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Justin K Terry, Benjamin Black, Mario Jayakumar, Ananth Hari. Luis Santos, Clemens Dieffendahl, Niall L Williams, Yashas Lokesh, Ryan Sullivan, Caroline Horsch, and Praveen Ravi. Pettingzoo: Gym for multi-agent reinforcement learning. arXiv preprint arXiv:2009. /4471, 2020.
12

---

Published as a conference paper at ICLR 2022
Gerald Tesauro. Temporal difference learning and td td-gammon. Communications of the ACM, 38(3): 58-68, 1995.
Güliz Tokadli and Michael C. Dorneich. Interaction paradigms: from human-human teaming to human-autonomy teaming. (DASC), pp. 1-8, 2019.
Dari Trendafilov, Daniel Polani, and Roderick Murray-Smith Model of coordination flow remote collaborative interaction. In 2015 17th UKSIm-AMSS International Conference on Modelling and Simulation (UKSim), pp- 361-366. IEEE, 2015.
John Tsitsiklis and Benjamin Van Roy. An analysis of temporal-differenc learning with function approximation. IEEE transactions automatic control, 42(5):674 1997.
Oriol Vinyals, Timo Ewalds, Sergey Bartunov, Petko Georgiev, Alexander Sasha Vezhnevets, Michelle Yeo, Alireza Makhzani, Heinrich Küttler, John Agapiou, Julian Schrittwieser, et al. Starcraft ii: A new challenge for reinforcement learning. arXiv preprint arXiv:1708.04782) 2017.
Tonghan Wang, Jianhao Wang. Yi Wu, and Chongjie Zhang. Influence-based multi-agent exploration. CoRR, abs/1910.05512, 2019. URL
05512
Ying Wen, Yaodong Yang, Rui Luo, Jun Wang, and Wei Pan. Probabilistic recursive reasoning for multi-agent reinforcement learning. In International Conference on Learning Representations, 2019. URL
Ying Wen, Yaodong Yang, and Jun Wang. Modelling bounded rationality in multi-agent interactions by generalized recursive reasoning. In Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI-20, pp. 414 4214, International Joint Conferences on Artificial Intelligence Organization, 2020.
Jiachen Yang, Alireza Nakhaci, David Isele, Kikuo Fujimura, and Hongyuan Zha. Cm3: Cooperative multi-goal multi-stage multi-agent reinforcement learning. In International Conference on Learn- ing Representations, 2020. /ttp::tt////eeeereree net htr://oruummumm 2tterrrooommm0011110000000
Kaiqing Zhang, Zhuoran Yang, Han Liu, Tong Zhang, and Tamer Basar. Fully decentralized multi- agent reinforcement learning with networked agents, In (ICML), pp. 5872-5881, PMLR, 2018.
13

---

Published as a conference paper at ICLR 2022
A APPENDIX
A.1 INFOPG PSEUDOCODE
Here, we provide a pseudocode to train our MI maximizing PG algorithm, InfoPG, in Algorithm
|
Algorithm 1: Training the Mutual Information Maximizing Policy Gradient (InfoPG).
I: Input: Number of agents, NN, maa_aaaee max__ccles and agents' level of iterated rationalizability. K
2: Initialize: For all agents (#roes T Toot #ott and {Vi, V2 VN}
3: while not converged do
4: for
to marr maa__cycls do 5: Reset environment and receive initial observation set: {ot, or ... of
6: for i 1 to N do
7:
Sample initial "guess" action: dj 1.(0) end for
menc (*1 of), where T'ne Tist
8:
9:
for k 1 to K do
10:
for i = to N do
11:
Identify neighbors by obtaining neighhor list, j Ai, using the adjacency graph, 9r Sample MAP: a; (k) T:mm (* a, (kk-)) {az (kk-)) end for end for
12:
| E Ai)), where F.om. E T
13:
14:
Step through environment using {a. 1.kk) 2.(k)
A1,(k) J. and receive next states and
a
rewards: {ol o ... o4th fr ri, t for to do
17:
A r + V'(ol+1) - ('(o
18:
VMja: = ReLU(A()
((()))
((h)) ...)) % For Adv. InfoPG remove the ReLU
19:
VV (A;)²
20:
Update: #B0t = not + 17 V
21:
Update: V = V + VV
22:
end for
23:
[ot, of ....... ) = fol41: o2+1 (.
24:
end for
25:
end while
Consider MAF-Dec-POMIP introduced in Section 3 with N agents where each agent is equipped with an encoding and communicative policy (Tenc and Teom. respectively), such that Toot [Teney Tcom] (lines 1-2). At the beginning of a new rollout, and for each timestep, t, within the allowed maximum number of steps, mar_cycles, each agent i receives state observation of from
the environment and produces an initial "guess" action, a; (.) using its encoding policy (lines 5-8). Each agent i has neighborhood of agents the number of agent i's physical neighbors (i.e., within close proximity). Accordingly, agents obtain the list of their neighbors by using the adjacency graph, G. (line 11).
communicate with, shown with j A where [
Next, depending on the specified level of iterated rationalizability in the decision hierarchy, K, agents communicate their action guesses higher-dimensional latent vector distributions with their neighbors K times and update their action guess iteratively using their communicative policy (line 9-14). The level-k action is then executed by all agents and a local reward is given to each agent separately (line 15). This process continues until either the environment is solved successfully, or the allowed maximum number of steps, mar_ pccccss has been attained. For each timestep, t, of the policy rollout and for each agent i, first the advantage value, A3, is computed using the critic network (line 17) and then, the gradient of the log probability is computed and scaled by the instantancous advantage (line 18). Note that the ReLU function in line 18 is proposed to enforce the non-negative reward feedback condition InfoPG, Eq. 3 However, other mechanisms could achieve the same effect (e.g., shaping the reward function to only include positive values). Line 19 is showing the gradient of our value estimate. The loss for our value estimate ((s,) is the cumulative discounted rewards subtracted by the true value of 8t, which is the advantage (the TD emrr).. Therefore, the
14

---

Published as a conference paper at ICLR 2022
gradient in line is the sum of squared individual advantages. Next, the encoding and communicative policies are updated (line 20) and eventually, the critic network is updated (line 21). This process repeats until convergence of the cumulative discounted rewards across all agents. We provide our code at htttpp://ggthub.....t thub. Ctw.ouue.oc///Ce--eeeaeaa Robot cs Labb TPP
A.2 INFOPG FOR CONTINUOUS ACTION-SPACES
To deploy InfoPG in continuous -paces, we follow common practice for continuous action- space actor-critic methods. Continuous policies are presented as probability distributions with floating values a certain range (e-g.. (-1, 1)). In this case, in order to facilitate exploration we will sample agents' actions from a normal probability distribution. As such, in continuous action-spaces, the policy network (Actor) will normally have two output heads, instead of one. The two outputs of the policy network are μ and a, the mean and standard deviation (STD) of the probability distribution, respectively. The sampled actions will be centered around the μ and the a determines on average, how far from the center the sample values will be. As the network gets more certain, the gets smaller, meaning that we tend to exploit good actions rather than exploring.
In discrete action-spaces the loss-function action-spaces, the bog-probability of a normal distribution used, as shown in Eq. 14
based on the log-probability (Eq. 3) In continuous
loga, (a|s) (x - 1²² logv2To²
(14)
20
In Eq. 14] the first and second term are the negative log-probability and the entropy bonus, respectively. By substituting the bog-robbbbility of the normal distribution in Eq. [4] back into the original InfoPG objective in Eq. 2 we can directly deploy the InfoPG objectives in continuous domains, such as the introduced Mulüwalker (Section 5). Note that, in practice and for simplicity, the policy network can only output the mean value, μa, while the STD value is fixed to a reasonable constant. Finally, to compute the MAP action for continuous action-space (Line 12 in Algorithm [ note that, theoretically, the MAP action for continuous space is just the mean action without any standard deviation from the normal distribution.
A.3 INFOPG OBJECTIVE FUNCTION DERIVATION (Eq.
The InfoPG definition as presented in Eq. consists of a summation across all agents within the communication range. This equation is a simplification from the original form which uses the assumption of independence between each agents' (k- - 1)-level action probability distributions. To arrive at the InfoPG objective function in Eq. _ of the conditional distributions across all neighbors to summation of log probability across all neighbors. The process can be shown as in Eq.
we start from Eq. [5 and convert the log probability
V lstoPG ((0)
E. ioc
Go Vo log(Tion ((a) VVo
(V la (0 at. a1.(k-1)),,)) ,63))
(15)
Bit
Goloi, ai) a log(
II II (ao ((b) 1110-11) a () oil)
(16)
0-
E.g Foo
Gilor at)
Vo loggg( (a) (a (1--2) 2.10-11 (.(0) (.00) .f))
(17)
jEA
A.4 CONVERGENCE PROOF SKETCH FOR EQ. 2
Following the approach in prior work (Bhatnagar al., 2009 Zhang et al. 2018), we present a convergence proof sketch for InfoPG through the Two-Time-Se SSale (TTS) stochastic approximation method, proposed by Borkar 1997p. We note that the convergence proof for InfoPG closely follows the general Policy Gradients (PG) convergence approach presented in Bhatnagar et al. (2009) and
Zhang et al. (2018), and we therefore only focus on presenting the core idea underlying convergence of InfoPG with k-level rationalizability. Herein, state that since InfoPG and Consensus Update (CU) share the graph-based local communication and the fully-decentralized actor-critic training paradigm, all assumptions made by Zhang al. (2018) also apply to work and therefore,
15

---

Published as a conference paper at ICLR 2022
directly adopt the set of assumptions (i.e., specifically, assumptions 4.1 4.4) presented in Zhang et al. (2018) without restating them.
For actor-critic algorithm, e.g. InfoPG, showing convergence of both the actor and critic simulta- neously is challenging because the noisy performance of the actor can affect the gradient on the critic and vice versa. As such, leverage the TTS approach, which states that in PG methods, the actor learns at a slower rate than the critic (Borkar 1997). Therefore, according to TTS, we can show the convergence of InfoPG in two steps: (1) first, we fix the policy and analyze the convergence of the critic and, (2) with a converged critic, we analyze the convergence of the actor.
Step 1: Critic Convergence We use bar notation in the following to denote vectorized quantities across agents in the environment such that, fg [mg..... T where N is the number of agents. Moreover, level-k policy in InfoPG includes two parts: a state-conditional policy level and an action-condie eition-conditional policy for higher levels of k. InfoPG first applies the level zero state- conditional policy to get the initial "guess" action and then recursively applies the action-conditional policy k times to recursively improve the level-k action-decision. We can show this process as (..((==)) (.(220)
T - =
(s!) PG seeks to maximize the objective function J(O), shown in Eq. 18
where de (3e) denotes the stationary distribution of the MDP and Rt denotes the joint reward function, including local rewards for each agent. Additionally, we denote the transition probability of the MDP as p( F oz). Since the formulation of PG objective in Eq. 18 is biased, it is commonly replaced with the unbiased estimate of the rewards, or (5,, āe) (Se, ae). as shown in Eq. 19
J(0) Σ
(s)))
Σ
(a(a))3)) R(3,,a))
(18)
8,68
a.EA
Σ (s))
To (ar(())) * (Q(5), @z) V(s))
(19)
$
a.EA
The unbiased estimator in Eq. 19 can be replaced with the state-value function by using the recursive definition of the action-value function (Sutton & Barto 2018). This substitution results in form known as the TD-error (Sutton 1985). where the bracketed term in Eq. i the TD-error
Q(5 at)
a.) +B((1))
(20)
Bind aino
J(0) = Σ (s) Σ S G.EA
no(at Ri3 + +y Σ 31, (()4)) (B+)
(21)
#111E8
Next, following the prior work (Bhatnagar al. 2009 Zhang al. 2018), we assume linear function approximation since the TD-learning-baa based policy evaluation may fail to converge with nonlinear function approximation (Tsitsiklis & Van Roy 1997| Zhang et al. 2018). We note that the value function is a mapping of states (of some dimensionality) to R. Therefore, we define V(.) 3 ((5r), where is a one dimensional weight vector and ((5.) ) is feature map that transforms the state vector to RK 6(5,) = [Ø1 (3)). ....) Óx (3t).. Now, following Bhatnagar et al. (2009). we define the Ordinary Differential Equation (ODE) associated with the recursive update of via Eq. 22 which then can be simplified to Eq. 23 using a matrix notation described in the following.
Σ (s) Σ (a(()()c)*
R( az) +7
Σ 51+155
aB (55 + 1) TT ((.)))
(22)
acEd
à +" -(T(
(23)
Finding the asymptotic cquilibrium of the critic, w is equivalent to solving the above equation, when à O, which is simplified when switching to matrix vector notation described below:
1. D S is diagonal matrix with dx (3x) for all E S as its elements.
2. P E ((||i is the probability matrix where p(5++1 |5,, a (5, represents an individual element.
16

---

Published as a conference paper at ICLR 2022
3. Φ I 5] K is the feature map whose rows are ((5)) for all S.
4. RISIX[AI a matrix where R(5;; @t) represents an individual element.
5. Ω E IR K|x[R| is a diagonal matrix with discount factor y as its elements.
6. : IN - R
N is an operator which is a mapping of the form: T(Ø) = PSW.
Next, following Zhang et al. (2018), we make two assumptions that apply to InfoPG and are essential to the rest of the convergence proof presented in the following.
Assumption 1- The update of the policy parameter includes a local projection operator, I IR X C R.V, that projects any A onto the compact set X- Also, we assume that X is large enough to include at least one local minimum of J(Ø).
Assumption 2 - The instantaneous reward r is uniformly bounded for any i e N and t 2 O. We note that the reward boundedness assumption is rather mild and is in accordance with prior work (Zhang et al. 2018)
In analogous matrix- notation, and under the aforementioned assumptions made above and by Zhang et al. (2018), for static policy in the TTS convergence setting, the lim W "" almost surely, where wh satisfies the equilibrium constraint a = 0 shown below. We note the solution seen below satisfies similar convergence equation as seen in Bhatnagar al. (2009).
e "" D(T(()))) (0x)) =0
(24)
= - DT((""") = = DO"
(25)
The above ODE explains the rate of change of the critic, and when the derivative reaches zero, the critic has reached stable equilibrium, and therefore, has converged.
Step Actor Convergence - According to the TTS (Borkar) 1997), for the actor step, we assume fixed, converged critic and show stabilized equilibrium of the policy. We assume there exists an operator, r, which projects any vector x E R + X C RRN, where X represents a compact set bounded by simplex in R.N. The use of this projection is critical to the convergence of stochastic TTS algorithms as stated by Bhhatagarr et al. (2009); Zhang et al. (2018), since policies that exist outside of the set can cause unstable equilibrium. Empirically, we apply the compactness of the set of policy gradients by defining a maximum gradient norm, as stated in A.8 In Eq. 26 we define the operator for the vector field x(.) E 8, which is assumed to be continuous function.
T(y + qr(ly)) -
(x((v))= = lim
(26)
"
the above limit does not converge to a singular value, we state (x())) results in set of convergent points. With this notation we state the ODE of the policy, after being projected onto a compact set, and note that given the assumptions made above and by ZZang et al. (2018), PG almost surely moves Ø to asymptotically stable equilibrium that satisfies the below Eq. 27 This proof analogy closely follows the single-agent convergence proofs presented in BBhttnggar et al. (2009) and Tsitsiklis & Van Roy 1997). Nevertheless, in our work, convergence While the TTS approach assumes the critic to have converged, the critic does not need to be a perfect estimator. With small approximation error, [Bhatnagar et al. (2009) proves that the below equation still converges within the neighborhood of the optimal concatenated, joint policies for all agents. The below ODE defines the derivative of the policy over time, and as the derivative approaches zero, the actor reaches stable equilibrium (or a set of equilibrium points, since in a fully decentralized setting, the actor is a vector of joint policies for all agent, as described in Section Bp and thus, convergence of the actor is achieved.
stationary point for all agents is the goal.
i = Es,-d dirttt Vog((T)) * (Q(5),, ax) - V (3x)) =
(27)
A.5 FULL PROOF OF THEOREM
Here, we derive the full proof of the Bayesian expansion of the policy (Theorem []. As mentioned before, given the Bayesian nature of the k-level hierarchy, actions conceived at sumilar levels of can be reasonably assumed to be independent. Without loss of generality, assume scenario
17

---

Published as a conference paper at ICLR 2022
with two cooperating agents i and both with k levels of rationalizatton. An important notational difference that will be used here is p(.). Policies are conventionally considered state- nate-conditional distributions of actions, where the action is the random variable. A specific action is usually either sampled from the distribution or the MAP action is selected. Here, we denote p( (X) to refer to the probability distribution of particular random variable X. Note that, evaluating p(X x:) returns the specific probability that X = I (and not a distribution). In the following, we seek to determine the distribution of actions, for at each level & using p(.) notation. This is determined by marginalizing the level-k action of agent i across any specific action that i or might take, which will be denoted as and y respectively. Additionally, a specific observation in the observation space will be denoted as z. Accordingly, we can represent the probability of action for agent at time / across levels of rationalization, {0, 1,.., K} as shown Equations
28 30
((a)
Σ p(a):00) 1 =2)p(o; = 2)
(28)
EE8
pla) ΣV Σ
p(a;
(()10)) a,
(1)) (())
= y) 2, o.00 y)p(a, 2010) x, at 2.(0)
(29)
REANEA
p(a (0) = ΣΣ
plab:k)) (0))
21(k-1) = 2, at 1. = y)p(a, 1.(k-1) x, a. 1.(k-1) = y) [4
(30)
ZEAVEA
At each level k 2 1, the probabilities of actions are directly proportional to the probabilities of i's and j's actions at level k- - 1 actions. Next, we can re-arrange the following Bayes' rule, from 31
to Eq. 32 to determine the probability of the joint distribution of the priors p(a
1.(k-1) jk () )
pla | 1a .g (1)--1))- play (.0--1) 1) i((--)) 1)
(4))
1.(k-1)
(31)
p(a (1 dl (1)-))
p(aj.(t-1 ol 1 pla 1) 1) at Gi(k-
oi (k) 1paaf (.10))
(32)
p(a di Og 1))
1(( jilk
Eq. 32
can be substituted back into the joint probability of the priors, pla; ((k-11)
ag 1.(k
1)
in Eq.
30
p(a, (.0k) = Σ Σ
p(a;
(.(k)
|
1)(
x, a
1,( =y)p(
ZEA DEA
p(ag.a1)) sikk
1,(--1)
I. oz. 1) y (1))
(33)
plaz.(1)
| aa
x,
v)
Now, move the term p(a: (0)) outside the summations, as it does not depend the marginalization,
and multiply both the numerator and denominator in Eq. 33 by the joint probability of the priors,
pla i.(k-1) = x, oz (k(k-1) = v). to arrive at Eq. 34
((a):00) = (()) ΣΣ Σ p(az:(k) a.((k-1)) x. (( =ypp(
zEAVEA
p(a (1 = x, a. (.6--1) = ji(k-1) y)
at 1((k-1) = x. (.1 = az (())
plo
(. x, al (1)--)) v)p(a, ((k--]
2x 0
(34)
Next, by simplification of the denominator we arrive
p(a, (.(k)) = =((af.())
ΣΣ ((k))
play
|
i,(k-1)
xr, ag
j((k-1 1) = =v)p(
ZEAVEA
=x a, 11(k-1) = cbi(k)) ((a),(0-1) = x, a f((k-1) = y)
a,
i((k-1)
plaz a (i(k-1)
sr a. (i(k-1) y)
(35)
18

---

Published as a conference paper at ICLR 2022
To simplify 35 first consider the transitivity of conditionals for the first two terms inside the summations. Note that, for a specific Bayes' tree in the form of our information graph shown
in Fig. 1 we can write ΣzE Eye (.(k)
|d, |a ,
<.(k-1) (.(k-1)) p(a, (((k-) aa 1.(k-1) (2
(.(k) df ) Next, considering the summations, we marginalize both the numerator and the pla
denominator in Eq. 35 across the joint action space. Accordingly, the numerator will simplify to since we are summing the probabilities for all actions. Also, the marginalization across the joint
action space to the denominator is simplified to p(at p(ap(() dz
2.(8-1)) o (k-1) = p(az.(e) As such, by
substituting these simplifications in Eq. 35 we arrive at Eq. 36
p(ap(h))
p(ae (.(0))
p(ay (.())
at
(.(0)) = p(at 8.(k)
at ((((k)
(36)
plat((h))
(((R) In this form, we join parallels between p(at (a)) and mior(a) (a 1). The T (4; (.()) |-) is the
probability distribution of the k-level action (.(0) which according to the initial definition, is
exactly the same as p(a, (()))))) (same applies for (()).(())) Additionally, in the derivation of p(a).())
a.-(k-11); however, notice that this probability is exactly the same as cmom (ag.(k) a, (.(6-1) .a. (,, therefore, we can make the following equivalencies and substitutions for both agents and j.
af (,(()), we used p(a.i(h) aj 2.(k-1)
(a (a) |)) ((a):()) Toom (az di (2(())
(37)
Now, considering that agent acted on its k-level reasoning and executed the MAP action, the log probability and its gradient of the action-distribution at the k-th level can be described as in Eq. 38
39
log(T (a).(h) MAP
-)) log(T i (ai MAP
com
dg MAP))
(38)
V log (a. (.(K) = MAP .)) v log( (az
5.(k) MAP of g.(0) MAP))
(39)
As such, we arrive at the conclusion that was arrived upon near the end of Section 4.4 performing gradient ascent on Tiat inherently increases Téoy (at
(((k)) af af-00)). This fact is used to support the
mutual information bounds derived in Theorems and and is valid for any & 2
A.6 DISCUSSION ON THE UNIFORMITY OF PRIORS ASSUMPTION
Similar assumption of uniform priors as ours in Section 4.5 have been used previously by Prasad (2015) for the calculation of MI upper-bound. In our work, we defined p(a:) as marginalization of the action-conditional policy, (a" across any potential a². The marginal's conceptual meaning here is similar to asking the question, "What should the probability of a² be, if we did not know a² ?" For given action-conditional policy, could expect a' to be uniformly random because the action-condittonal policy is expected to only change the probability of a selected action based on the levevel reasoning with other agents. If there is no action to reason upon, the agent has no information with which to base its k--th action upon. It is important to note here that p(a') is not a marginalization of both the stateeconditional and action-conditional policies. Since p(a') is only marginalization of the action-conditional policy, we view the uniformly-random prior assumption as reasonable design choice.
A.7 SUPPLEMENTARY RESULTS
In this section we provide our supplementary results. We start by analysing and interpreting agents' communicative policy in our fraudulent agent experiment in order understand the effect of k-level rationalization for decision- making in this scenario. Next, we present the agent-level performances for InfoPG and compare with the baselines in all three evaluation environments. Next, we present an scalability analysis in the Pistonball environment to investigate robustness to larger number of agents. Eventually, we conclude this section by presenting a list of takeaways.
A.7.1 POLICY INTERPRETATION FOR THE FRAUDULENT AGENT EXPERIMENT
In this section, we present analysis and interpretation of agents' communicative policy in our fraudulent agent experiment in order to understand the effect of k-level rationalization for decision- making in this scenario. We test the learnt policy at convergence using Adv. InfoPG in the fraudulent
19

---

Published as a conference paper at ICLR 2022
(a) Action distributions for pistons at =
piston
piston 1
piston 3
piston 4
1.0
1.0
1.0
1.0
Probability
Probability
Probability
Probability
0.6
0.5
0.6
0.6
0.0
0.0
0.0
0.0
U
Actions
Actions
Actions
Actions
(h) Action distributions for pistons at f =
10
piston
piston 1
piston 3
piston 4
Probability
0.8
Probability
0.8
Probability
0.8
Probability
0.8
0.6
0.2
0.2
0.2
0.2
Actions
Actions
Actions
Actions
(c) Action distributions for pistons
piston 0
piston 1
piston 3
piston 4
1.0
1.0
1.0
1.0
Probability
0.8
Probability
0.8
Probability
0.8
Probability
0.8
0.4
0.4
0.4
0.4
0.0
0.0
0.0
0.0
Actions
Actions
Actions
Actions
(d) Action distributions for pistons f
32
piston
piston 1
piston 3
piston 4
1.0
1.0
1.0
1.0
Probability
Probability
Probability
Probability
0.6
0.6
0.6
0.6
0.2
0.2
0.2
0.2
U
U
u
5
U
Actions
Actions
Actions
Actions
(e) Action distributions for pistons at /
=
37
piston
piston 1
piston 3
piston 4
Probability
0.8
Probability
0.8
Probability
0.8
Probability
0.8
0.4
0.4
0.4
0.2
0.2
0.2
0.2
Actions
Actions
Actions
Actions
Figure 4: Action distributions of piston agents across 37 timesteps for the fraudulent agent experiment introduced
Section Note that Piston 2 (not displayed) the fraudulent agent with untrainable random policy.
20

---

Published as a conference paper at ICLR 2022
agent experiment, presented in Section 6 The results shown in Figure 4 in which, we present the action distributions of agents before and after rationalizing their decisions with their neighbors through k-level reasoning. For each action distribution graph, the Y-axis is the probability of an action and the X-axis represents actions, where ==move up, d=move down, and s=stay constant.
In Figure 4 we present sample illustrations of test run in BGP scenario for t 0, 10, 25, 32, 37, from start to the end of the episode. At t = 0 (Fig. 4a we can see that the episode starts with the ball on top of the right-most pistons (i.e. pistons 3 and 4). Note that pistons are indexed left to right. With k = 1 reasoning, we show piston 3's rationalization for its action decision in three phases: first, aPs.(k=0), is the naive k = O action (blue); second, a22,3.(k=1), is the h = 1 rationalization that incorporates piston 2's random action (orange), and, third, aP2,,..(k=1), is the k 1 rationalization that incorporates both piston 2's random action and piston 4's k 0 action into piston 3's k- = 1 action decision (pink). Using similar notation convention, a=3,4.(k=1) is piston 4's action rationalization given piston 3's k = 0 action rationalization. Now, notice that the spread of (p=((==0) at is relatively uniform (blue), and given that piston 2 randomly moving, a=2.:(k=1) remains unchanged (orange). This indicates piston 3 has learned to ignore piston 2, which is the fraudulent agent. Additionally, notice that Q=4.(k=0) at t 0 is bimodal and has relatively equal probabilities of moving either up or down; however, we can see for both pistons 3 and 4, after rationalizing their actions with each other k 1, both action distributions become unimodal and tend towards moving up, which is the desired action for moving the ball to left.
This coordination demonstrates an interesting strategy; piston 3 and piston 4 have learned that coordinating actions with the randomly moving piston 2 is not desirable and therefore, they seek to move the ball high as possible, and toss it over piston 2. Empirical proof of this behavior can be seen by the continuation of the spread of distributions at t = 10. At t 25 a distinct change occurs; piston 3's action distribution, after k rationalization with piston 4, becomes uniform again, while Piston 4 is still unimodal and tending up. We believe this behavior shows that piston 3 and have realized the strategy to bypass piston is to "launch" the ball over piston 2, which can be accomplished by piston 4 moving up, while piston 3 remains stable, effectively creating a leftward force for the ball to move left. At = 32 we can see the "launching" is performed, and here the action distributions of both piston 3 and 4 become relatively uniform again (Note that actions of piston 3 and 4 do not matter at this point since they are not directly located under the ball and therefore, do not receive reward for their actions). From = 32 to t 37, the ball traverses over pistons 0 and 1; however, note that piston O and 1 will not need to move the ball too much, since the ball already has leftward momentum. Accordingly, piston 0 and 1 only need coordinate create a leftward ramp to facilitate ball's movement. As such, both piston O and piston follow relatively uniform distributions after k=0 and I rationalization. At 37, the ball is over piston and has reached the left wall, which denotes winning and end of the episode.
In summary, we show two key behaviors learnt by agents through our Adv. InfoPG in the fraudulent agent experiment: 1) Piston 2 is untrustworthy and thus, coordinating with this agent is not desired, which leads to unchanged this fraudulent agent. 2) Pistons 3 and 4 learn to avoid the fraudulent agent (piston 2) by "launching" the ball over it, giving the ball a leftward momentum to reach the left wall.
distriiuiitissssonnn for Pistons 3 and I after iterated kelevel reasoning with
A.7.2 A QUALITATIVE ANALYSIS FOR BOUNDED RATIONALITY
The postulate of lelleeel reasoning is that higher levels of k should allow for deeper decision rational- ization and therefore better strategies. In this section, we qualitatively investigate different examples of intelligent behavior induced by varying bounds of rationality. To address this, we specifically further investigate InfoPG's 's results in the Multi and StarCraft (SC2) domains due to their complex mechanics and multi-faceted objectives. In the following, we first present our qualitative analysis for SC2 and Multiwalker, respectively.
SC2 Our qualitative analysis in SC2 is demonstration of how bounded rationality and higher levels of iterated reasoning benefits performance. In SC2, agents are positively rewarded for shooting and killing enemy agents, and are negatively penalized for getting shot at. Therefore, locally optimal strategy is to run away from the enemy team to avoid any negative penalties, while a globally optimal strategy is to kill and eliminate all the enemy agents achieve high positive rewards.
21

---

Published as a conference paper at ICLR 2022
(6.1) - InfoPG, (k = 0)
(6.4)- (k = 1)
forming a triangle
formation to fight
Our agents
Enemy agents
agents
agents
122)-Im) (6.2)-Infor)) (k 0)
- (k 1)
Our agents (red) running avoid getting
Sacrificing the front- agent while the remaining agents
(6.3) InfoPG, (k 0)
(6f6)_ (k 1)
agents (red) manage scape do not fight back
righting and eliminating the enemy
Figure 5: Comparing the learned policies by InfoPG at convergence in the SC2 domain with & = 0 and k = 1. With k = 0 (Fig. 5.1-5.3), the naive agents disregard other agents actions and simply learn to run away to avoid the negative penalties of getting shot at. This is while the sophisticated agents with & (Fig. 5.4-5.6), learn more strategic policies to work together to eliminate the enemy team and achieve high positive rewards.
Fig. (ig-3sshwss our qualitative results for analyzing the effects of assuming bounded-rational agents and iterated reasoning in the SC2 domain. We compare the learned policies by InfoPG at convergence in the SC2 domain with and 1.
At k = 0 of the rationalization hierarchy, the fully naive and non-strategic level-0 agents choose actions while completely disregarding other agents actions (i.e., have zero-order beliefs). As such, for a level-0 policy, we expect to observe that agents simply run away from the enemy to avoid getting shot at, since single agent does not believe (zero-order belief) it can overcome the enemy team. As seen in Fig. 5.1-5.3, the naive agents expectedly only learn to run away to avoid the negative penalties of getting shot at. This fleeing behavior allows agents to maintain a reward of zero, as shown in Fig. indicating successful escape and convergence to the locally optimum solution.
At level k = 1, each agent is now more sophisticated and believes that the other agents have a level-O policy and takes actions according to that. In this case, we observe vastly different behavior. As shown in Fig. 5.4-5.6, agents here learn more strategic policies to work together to eliminate the enemy team and achieve high positive rewards. The agents begin triangle-like formation towards the enemy (Fig. 5.4). Enemy agents then begin to shoot the closest opposing player at the front of the triangle formation. The other agents in the team
this opportunity and start firing the enemy team while they shoot the front-most agent. As such, the remaining two agents manage to kill and climinate the enemy team. Through reasoning their level-1 actions based on their teammates level-O action, InfoPG agents learn a sacrificial technique of exposing one agent as bait, which allows the agents to converge to the globally optimum solution of killing the entire enemy team. This is also reflected in Figure where the k = 1 InfoPG achieves the highest cumulative rewards.
Multiwalker Our qualitative analysis Multiwalker is another demonstration of how higher levels of iterated reasoning benefits performance. There are two objectives that the walkers need to satisfy: (1) stabilization (both the package and the walkers) and (2) moving forward. Stabilization of the package and the walkers are the primary goals, since dropping the package, failing the game with a penalty. Walking (i.c., moving forward to the right) is an additional goal, since every forward step yields small proportional reward. Ultimately, the walkers should aim to achieve both stabilization and walking at the same time, which is the globally optimum solution.
falling, results in
Fig. shows qualitative results for analyzing the effects of assuming counded-rational agents and iterated reasoning in the Multiwalker domain. At level & = 1, each walker believes that the other walker has only level-0, non-rational policy. We observe in Fig. (a) that, with InfoPG and by
22

---

Published as a conference paper at ICLR 2022
Agents failing moving forward
Agents can slightly move forward
Agents can move forward
Learned policy: Splits
Learned policy: Wiggle Forword
Learned policy: Walk Forword
(a) InfoPG, k=1
(b) InfoPG, k=2
(c) InfoPG, k=3
and l Fig. Sa-Sc, respectively. With l: agents only learn perform split to balance the package top and avoid falling. This is while with agents learn quickly walk forward. middle stage of rationalization. k = 2, achieves an in-between policy where agents split to balance, but also wiggle forward slowly.
Figure 6: Comparing the learned policies by InfoPG in the Multiwalker with & =
1, the walkers solve only the stabilization problem by learning to do the "splits", which is locally optimum solution. The walkers create a wide base with their legs and simply hold the package statically with no forward progress (evidenced by the starting red flag). This technique requires some degree of coordination since the walkers have to do the splits synchronously at the beginning of the experiment; however, this is not nearly complex enough strategy to achieve any positive rewards. Looking at the reward convergence in Fig. 2 h 1 achieves converges to the locally optimum solution and achieves a reward of 0, since the walkers do not get any positive reward for moving nor do they get any negative reward for dropping the package falling.
At level & 2, each walker now believes that the other walker has a level-1, bounded-rational policy. Intuitively, assuming
sophisticated policy for a teammate should lead to better overall strategy, since the best-response solution to such sophisticated policy needs a certain level of sophistication (eriicaationGrrsmmaan Gershman al. (2015) : Ho & Su (013). We observe in Fig. (b) that, expected, the learned policies at level & = of rationalization still includes performing the "splits" for balancing while agents also learned to wiggle forward slowly and receive some positive reward.
As we increase the rationalization depth from k = 3, we see in Fig. (C(c) that the walkers not only stabilize the package, but also start moving forward (evidenced by the starting red flag out of frame) with much more sophisticated strategies. The left-most walker learns to generate forward momentum and walk more quickly than the front walker, which learns walk more slowly and maintain the stability of the package. Note that this illustrates the idea of role allocation, which is relatively complex strategy and indicative of higher levels of intelligence achieved through assuming sophisticated, level-2 teammates. The walkers learn to coordinate their movements, because if the left-most walker makes too jerky forward movement, the right-most walker adjusts by staying more static stabilize the package. In Fig. 2 the collective strategy at A: = 3 can achieve rewards as high as +10, which is the globally optimum solution.
A.7.3 SCALABILITY ANALYSIS: PISTONBALL
Here, we investigate InfoPG's robustness to larger number of interacting agents in the Pistonball environment. For this experiment, We selected our best-performing model, Adv. InfoPG, and the best-performing baseline, MOA (Jaques al.) 2019), from our primary results in Section 6 We increased the number of agents from five to ten and kept the communication range to be the same (i.e., one piston on each side). The results are presented Fig. 7 As shown, Adv. InfoPG outperforms MOA in both maximizing average individual and team reward performances during training.
InfoPG considers two way communication with each of its neighbors (there are A neighbors which communicated with & times). If D is the dimension of the communicated k-level action-vector, the bandwidth of input and output communication channels is ( (k))), where each communication channel is O A IDD). We leave the choice of | and D be hyper-parameters, all of which can be lessened as the number of agents increase to inhibit computational complexity issues.
A.7.4 AGENT-WISE PERFORMANCE COMPARISON
As mentioned, the objective a fully decentralized domain is to maximize the average return by each individual agent, such that the obtained cumulative team reward is also maximized. We have show in
23

---

Published as a conference paper at ICLR 2022
17.5
InfoPG [Ours]
Cum. Team Reward
15.0
MOA
12.5
10.0
7.5
5.0
2.5
-2.5
200
400
600
800
1000
Episodes
Cum. Reward
Piston
Piston 1
Piston
Piston 3
Piston
QVoL
Hong
500
1000
1000
500
1000
Episodes
Episodes
Episodes
Episodes
Episodes
Cum. Reward
Piston
Piston 6
Piston
Piston 8
Piston
Ourou
0.5
1.0
1.0
0.5
0.0
-0.25
-0.5
00.
500 Episodes
1000
1000
Episodes
Episodes
Episodes
Episodes
Figure 7: Scalability comparison between Adv. InfoPG and the best-performing baseline. MOA (Jaques al. 2019), in the Pistonball domain with interacting agents. Adv. InfoPG outperforms MOA in both maximizing average individual leam reward performances.
our primary results in Section O that InfoPG outperforms all baselines across all three domains in achieving higher cumulative team reward. Here, we present the agent-level reward performances for InfoPG and compare with the baselines across three domains. The results are presented in Fig. 8 where niguris Sa &d represent the individual agent performances Co-op Pong, Pistonball, Multiwalker and StarCraft II (3M), respectively. As shown, our InfoPG and its MI-regularizing variant, Adv. InfoPG, continually outperform the other baselines in maximizing achieved individual rewards for agents. Specifically, in all graphs for Adv. InfoPG, all agents maximize individual rewards over time, and Adv. InfoPG achieves SOTA across all baselines.
A.8 EVALUATION ENVIRONMENTS: ADDITIONAL DETAILS AND PARAMETERS
Here we provide additional details regarding the employed evaluation environments for training and testing InfoPG and cover the associated environment parameters related our experiments. An instance of the four environments are presented in Fig. 9
Cooperative Pong (Co-op Pong) Terry al., 2020) The objective in this game keep pong ball in play for as long as possible between two co-operating paddles. To fit the MAF-Dec- POMDP paradigm, agents must receive individualistic rewards. In the Co-op Pong domain, each paddle receives reward of +1 if it hits an incoming pong ball successfully and penalty of - if it misses. The game ends either when a paddle misses or if max mar__yycles 300 cycles have elapsed. Therefore, in order to continue receiving positive rewards of +1, paddles are implicitly encouraged to cooperate to maximize their accumulated rewards. For an episode the game, the pong ball was
pirelss] Since the set to move at a velocity of 15 pirels while the paddles move slightly slower at 1 sep. ball moves faster than the paddles, the paddles require "forecasting" their intended position when the pong ball comes into their field-of-view (FOV), which is a 280 x 240 RGB image. An important facet of this environment is the time-delayed nature of the actions. Consider scenario when the left-side
sec.
24

---

Published as a conference paper at ICLR 2022
(a) Individual agent performances in Co-op Pong.
InfOS (C
IntoPt Cc
IntoRss (K
Adv. IntoRC
NC-ACC
Paddle O
Paddle
0.3
0.3
Cum. Reward
Cum. Reward
0.1
0.1
-0.4
-0.4
Episodes
Episodes
(b) Individual agent performances in Pistonball.
Cum. Reward
buoubus w
Piston
Cum. Reward
Piston
Episodes
Episodes
Cum. Reward
Piston
Cum. Reward
Piston
2.0
1.5
0000000
Episodes
Episodes
Cum. Reward
Piston 4
b00000009
Episodes
(c) Individual agent performances Multiwalker.
Walker 0
Walker 1
Cum. Reward
Cum. Reward
-10
-10
-20
-20
-30
-30
200
400
600
800
1000
Episodes
Episodes
(d) Individual agent performances StarCraft II (3M).
StarCraft II Marine 0
StarCraft II Marine 1
StarCraft II Marine
3.5
3.5
Cum. Reward
3.0
Cum. Reward
3.0
Cum. Reward
3.0
2.5
2.3
2.5
2.0
2.0
2.0
1.5
1.0
0.5
200
400
1000
200
800
600
Episodes
Episodes
Episodes
Figure Individual rewards obtained by each individual agents across episodes as training proceeds evaluation environments. Our Adv. InfoPG continually outperforms all baselines (Wen el al. 2019 Jaques et al.
2019 Zhang et al. 2018 Sutton & Barto 2018) across all domains.
25

---

Published as a conference paper at ICLR 2022
(a) Pistonball
(b) Co-op Pong
(c) Multiwalker
(d) StarCraft II
Figure 9: Instances of the utilized multi-agent cooperative environments. Domains parts
of the PettingZoo (Tery al.) 2020) MARL research library and can be accessed online at https: /ttps://ww.... ingzo. m3 /envs. The StarCraft (Vinyals et al.] (017); can be accessed from Deepmind's repository available online at https: //g/ www.tttw..oooo..tteoo ccom/deepmii..ccccmcmmmemm/mmmmm pttpeeemma/ppcc...
paddle hits the ball at & this means that the right-side paddle will receive the ball at minimum, at 280 l2 1 + 15 This measure is underestimation, since the pong ball will not likely move in straight line drive (i.e. it may hit the sides of the walls) but it illustrates the point that the action of the left-side paddle at t is particularly relevant the action of the right-side paddle at t2: however, the action of the left-side paddle at l2 is not particularly relevant to the right-side.
Therefore, our experiments, to account for the time-delay in the action information, a "hub" was designed where the action at the time of the last "hit" is shared to the opposing paddle, and zero-vector otherwise. This procedure was applied for both InfoPG and MOA Jaques et al. (2019) as to fairly evaluate the communicative algorithms. In the case of MOA, the time-delayed action was sought to be "predicted" by the opposing paddle's 's model agent.
2) Pistonball (Terry et al., 2020) The goal in the this environment is to move ball from right side of the screen (c.g., right wall) to the left side of the screen (c.g.. .. left wall) by activating/deactivinn team of five vertically moving piston agents. The ball has momentum in motion and is elastic. In order to encourage robustness, the ball was randomly placed on the pistons with a friction factor of 0.3, mass of 0.75, and relatively high elasticity factor of 1.5. An episode of the game ends if agents move the ball to the left wall or after mcx__yclles = 200 cycles have elapsed. Each agent's observation is an RGB image of size 457 x 120 covering the pistons (or the wall) around an agent and the space above them. Each piston receives an individual reward which is combination of how much the corresponding agent directly contributed to moving the ball to left (i.e., with a value of xhhali X where X, represents the center position of the ball along the X-axis at time !), and negative time penalty
a
-0.007 per timestep. piston considered be contributing directly to moving the ball to left, if it is directly below any part of the ball. Given the ball's 's radius of 20 pixels, at each timestep, three pistons can be directly under the ball. Agents win an episode of the game they can coordinate efficiently to move the ball to the left wall within allowed maximum steps.
3) Multiwalker (Gupta et al., 2017: Terry et al. 2020 The objective this continuous-space environment is for team of two bipedal robots carry heavy package cooperatively and walk as far right as possible. The weight of the package depends on its length which is determined by the number of agents. We note that, the two-agent Each robot exerts a variable force on two joints in its two legs, and therefore, the action-space is of dimension four with values in range (-1,1) The bipedal robots receive local rewards related to individual balance and stability of their hull. The reward function includes reward of +1 for scaled forward displacement of each bipedal robot's hull. We set the maximum number of allowed steps to maz paaz_cclesseeeeee = 500 cycles, which would terminate at any point if bipedal or the package falls. If bipedal robot falls, will individually receive penalty of 10, and, if the package falls on the ground, each bipedal receives penalty of 1000 Each agent receives a 31 -dimensional observation vector. The first 24 elements of the observation vector represent the bipedal robot's internal kinematics and the rest (i.c, elements 24-31) relate to LIDAR observations of the package position as well as the position of the adjacent bipedals.
is the most challenging scenario in Multiwalker.
4) StarCraft II |Vinyals al. 2017) (The 3M (three marines three marines) challenge). The goal in this domain is for team of three friendly marines to find, shoot, and kill three enemy marines soon possible, without dying or getting hit (Seraj al. 2200 2019). This domains is more challenging than the previous ones since the state-space is larger and the communication graph is time-varying. In this challenge, marines move in four primitive directions and shoot enemy
26

---

Published as a conference paper at ICLR 2022
marine within distance (i.e., multiple enemy marines can be in vision at once), and therefore, the action-space dimension is also larger than the previous domains. Agents get negatively rewarded when they are shot by enemy marines and are positively rewarded when shooting enemy marines. 3M presents a fundamentally more challenging environment than Pistonball, Multiwalker, and Pong, as the state space is much larger, and agents arena. The action space is also larger (size 8) as agents can choose between: no action, moving in 4 directions, and shooting any one out of enemy marines. Additionally, agents have a time-varying communication graph (different from the other domains), because friendly marines move in and out of the line of sight.
allowed to move in 2D over large gameplay
A.9 TRAINING AND EXECUTION DETAILS
Under the MAF-Dec-POMDE paradigm, each agent i E N is equipped with its own optimizer and policy Ti.i which consists of an encoding policy T and communicative policy _ (each parameterized by 8*). The encoding policy can be represented using a feed-forward neural network, and the communicative policy can be represented by any class of Recurrent Neural Networks (RNNs), such as the Gated Recurrent Unit (GRU) or Long Short- Term Memory (LSTM). For computational efficiency, we chose use GRU simplistic RNN architecture.
Additionally, while we formulaically denote actions for level l as aj (k-(k-1) in execution we represent these actions these vectors are known as policy latent size in the provided hyperparameter tables. This parameter (also shared by other baselines) refers to the size of the latent vector prior to the final Softmax output layer. During the encoding stage of InfoPG, each agent, i, receives an observed state vector, of, and encodes an action vector a, (.(0) using n² Tenn-- During k-level communication, each agent receives the action vectors of neighboring agent j E A from level k- and performs a forward-pass on the RNN, where the initial cell state is a, (,(k-1) 1)_ The action probabilities for the discrete domains (i.e., Co-op Pong and Pistonball) are outputted by the feed-forward network where the last layer size is equal to the size of the action space and a Softmax activation. Note that for our continuous action-space domain, Multiwalker, the final Softmax activation function is replaced with the Tanh activation. Neighboring agents are determined using the adjacency graph Gr, and a distance hyper-parameter specifying how "far" agent i can communicate (i.e., communication range). Ge is an undirected time-varying graph, and as agents perform actions and change their relative position (depending on the domain), the edges& & S ((,,)) i E EN, i + j} are updated for the next timestep. This process is carried out until convergence of the cumulative rewards of all N agents.
vectors to maximize information during inference. The size of
Specifics for Co-op Pong The input observation in this domain, a 280 x 240 RGB image, contains information about where the pong ball exists in the FOV of each paddle. Since the ball is in motion, we found higher performance could be achieved by setting the observation at time, f, to be the difference between the observation at and - 1. As such, we encoded the input observation to represent information about not just the position, but also the velocity of the ball. This procedure was maintained for all baselines.
Another property we found critical to the performance of InfoPG agents in Co-op Pong was the type of RNN for π Toom- In Pong, rewards are rather sparse, since paddles only receive feedback when they hit or miss ball, while in other times and when ball is traversing the screen (which is the majority of the time spent in the game) no feedback is received from the environment. Accordingly, we leveraged curriculum learning (Bengio et al. 2009) such that we let agents first learn the mechanics of hitting the pong ball and then, learn the benefit of communication. We achieved this behavior by using a simple RNN (we distinguish this with VRNN for Vanilla RNN) cell for T where the initial weight matrix Wi, was set to the identity matrix and all other parameters were set to a small constant. This way, we effectively make the output of the T'om Th at the beginning episodes of training, while as time elapses, the weight matrix is optimized to incorporate actions from the neighboring paddle.
Specifics for Pistonball - The agents each receive a 457 x 120 RGB image as their observation input. In order to minimize feature size, each observation was first cropped to size of 224 x 224, normalized and inputted into a pre-trained AlexNet model. AlexNet (Krizhevsky et al., 2012) is a CNN that takes in images and outputs probability scores of classes. In our experiments, we utilized the first four intermediate layers of AlexNet to produce rich feature observations to the input of the encoding policy. This procedure was applied to all baselines.
27

---

Published as a conference paper at ICLR 2022
Hardware Specifies All experiments conducted on NVIDIA Quadro RTX 8000 with approximately 50 GB Video Memory Capacity.
Training Hyperparameters- We present the training hyperparameters in implementations and experiments across methods and three environments Tables 2
Table Co-op Pong Training Hyperparameters.
Experiments
Pong
InfoPG 4e-4
Ady InfoPG
NC-A2C
CU
MOA
PR2-AC
Learning Rate
4e-4
4e-4
4e-4
4e-4
4e-4
Size of Latent Vector
30
30
30
30
Type Com. Network
VRNN
VRNN
GRU
Epochs
4000
4000
4000
4000
4000
4000
MOA Loss Weight
0.1
Discount Factor
0.95
0.95
0.95
0.95
0.95
0.99
Batch Size
16
Max Gradient Norm
10
10
10
Replay Buffer Size
lc5
Number of Particles
16
Table 3: Pistonball Training Hyperparameters.
Experiments
Pistonball
InfoPG
Adv. IntoPG
NC-A2C
CU
MOA
PR2-AC
Learning Rate
Ie-
Te-3
1e-3
Ic-3
1e-3
Size of Latent Vector
20
20
20
20
20
20
Type of Com. Network
GRU
GRU
GRU
Epochs
1000
1000
1000
1000
1000
1000
MOA Loss Weight
Discount Factor
0.99
0.99
0.99
0.99
0.99
0.99
Batch Size
4
4
4
4
Max Gradient Norm
0.75
0.75
0.75
0.75
0.75
4.0
Replay Buffer Size
1e5
Number of Particles
16
Table 4: Multiwalker Training Hyperparameters.
Experiments
Multiwalker NC-A2C
InfoPG
Adv. InfoPG
CU
MOA
PR2-AC
Learning Rate
4e-4
4e-4
4e-4
4e-4
4e-4
4e-4
Size of Latent Vector
30
30
30
30
30
30
Type Com. Network
GRU
GRU
GRU
Epochs
1000
1000
1000
1000
1000
1000
MOA Loss Weight
0.1
Discount Factor
0.95
0.95
0.95
0.95
0.95
0.95
Batch Size
16
16
16
16
16
16
Max Gradient Norm
5
5
5
Replay Buffer Size
le5
Number of Particles
16
28

---

Published as a conference paper at ICLR 2022
Table 5: StarCraft Mini-game (The Challenge) Training Hyperparameters.
Experiments
StarCraft (3M Challenge)
InfoPG
Adv. InfoPG
NC-A2C
CU
MOA
PR2-AC
Learning Rate
lc-4
le-4
le-4
lc-4
lc-4
lc-4
Size of Latent Vector
50
50
50
50
50
Type Com, Network
GRU
GRU
GRU
Epochs
1000
1000
1000
1000
1000
1000
MOA Loss Weight
0.1
Discount Factor
0.99
0.99
0.99
0.99
0.99
0.99
Batch Size
64
64
64
Max Gradient Norm
6
6
6
Replay Buffer Size
le5
Number of Particles
16
Table 6: Pistonball Training Hyperparameters for the fraudulent agent experiment.
Experiments
Fraud Pistonball
InfoPG
Ady InfoPG
MOA
Learning Rate
le-3
le-3
le-3
Size of Latent Vector
20
20
20
Type of Com. Network
GRU
GRU
GRU
Epochs
1000
1000
1000
MOA Loss Weight
1.0
Discount Factor
0.99
0.99
0.99
Batch Size
2
2
2
Max Gradient Norm
0.5
0.5
0.5
29


Reviews:
[{"review_id": "kfLGkVfPG4", "reviewer": "Reviewer_4Fxp", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "While there are plenty of interesting ideas in this paper, and this kind of approach to multiagent learning that relies both on information theory and game theory seems to hold great promise, I find there are multiple issues with the paper that must be addressed for it to be of greater utility to the ML and RL communities.\n\n- First and foremost, it seems the authors omit from their literature review (and subsequently from their consideration of eligible baselines) works relating to two heavily relevant bodies of work: work on hierarchical learning in Dec-POMDPs (for instance Amato et al. 2019), and work on learning to communicate in multiagent RL (for instance Foerster et al. 2016, or Sheikh and Boloni 2019).\n\n- At the core, what the paper seems to propose, ultimately, is a framework for jointly learning to communicate *and* act simultaneously, which is both interesting and useful, but again, certain related work seems to be missing in that regard (consider Ghavamzadeh and Mahadevan 2004 as a relatively early - but still related - example). \n\n- A potentially critical consideration which the paper does not seem to explicitly address in its theoretical analysis is that it's unclear from the setting and the (rather muddled, more on that later) formulation of the algorithmic approach how the proposed framework avoids the plague of decentralized learning in multiagent RL, which is nonstationarity. In fact, it almost seems baked into the solution that if each policy learned is the best response to the policies at the lower level, then nothing is necessarily guaranteed to converge. There's also the risk that implicitly the extent of communication baked into the framework renders the approach analogous to single agent learning (theory of mind taken to its extreme), and it is unclear to me from the paper to what extent this might be the case (there is a proof in the supplementary material that eq. 2 does converge, but because the entire framework is so muddled - more on that later - it's not clear how that resolves the stability issue for the larger framework, and also, one cannot rely on supplementary material to establish key aspects of their approach).\n\n- in practice the communication setup proposed in the paper, as much as I can understand it, seems rather contrived and unrealistic. This may not be a disqualifying aspect of the approach - we often need to make certain simplifying assumptions to establish initial results and study novel approaches, but it does raise the question of how well this approach will hold up if certain constraints on communication are imposed. \n\n- Unfortunately my biggest issue with the paper is lack of clarity. Terms are introduced without sufficiently elucidating their meaning in the specific context of the paper (even as simple an example as \"rationalizability\" right in the abstract), Section 4.2 which should be the backbone of the paper is very confusing to read, Section 4.3 was even harder for me to follow, and ultimately by the end of Section 4, before discussing the empirical evaluation, while I retained a high level mental picture of the general outline of the proposed approach, I could not technically describe how the actual learning framework was designed, how the hierarchical approach works in practice, and how the framework is trained (the supplementary material helps somewhat, but not enough, and again, authors should not rely on supplementary material to present any key aspect of their work, they are called \"supplementary\" for a reason).\n", "summary_of_the_paper": "This paper discusses a hierarchical, iterated reasoning scheme for learning policies conditioned on the other agents' policies at that stage,  maximizing both the mutual information between agent policies and agent rewards. The authors leverage cognitive hierarchical theory wherein each agents has multiple levels of abstraction and reasoning about the actions other agents might take, and take a game-theoretic approach to policy learning in which each subsequent policy is the best response based on other agents' previous policies. The authors proceed to show this approach yields results which outperform several baselines in complex environments such as StarCraft II and multiwalker.", "summary_of_the_review": "This paper has interesting ideas but is lacking in how it anchors its contribution to related work and compares against it. More glaringly, this papers suffers from substantial lack of clarity both in terms of its theoretical grounding, and more critically, in terms of how it presents its core framework, how it is designed, and how it is applied. I believe it should be revised substantially before it is suitable for publication at a venue such as ICLR.", "strength_and_weaknesses": "", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "LHnWVHfkuNA", "reviewer": "Reviewer_SyxF", "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": "# Strengths\n- The paper is well written. For the most part, each section makes its points clearly and the paper is easy to follow.\n- Insofar as it is defensible (see Weaknesses below), the policy architecture seems straightforward and enables PG to implicitly target an MI metric associated with good coordination.\n- The authors provide both a theoretical analysis of InfoPG (although, again, see Weaknesses below) and empirical demonstration of its effectiveness.\n- InfoPG accounts for the possibility that not all agents provide meaningful communication.\n\n# Weaknesses\n- The abstract and introduction talk about bounded rationality, but that concept doesn't seem relevant thereafter.\n- Much of the paper is devoted to demonstrating the *implicit* connection between MI of agents' actions and the InfoPG policy formulation. This comes across as something of a *post hoc* motivation for the setup. It makes good enough sense why MI and coordination are related, but (as the paper points out) treating MI maximization as the objective is potentially short sighted. In sum, I question if MI is the best lens to motivate/understand this approach.\n- Good performance is encouraging, but the most relevant analyses for validating the intuitions of the method are largely ignored in the main text.\n- From the description in A.9, it sounds like the connection between *k*-level reasoning and the actual architecture implementation is misleading. It seems more appropriate to think of the agents' policies as one large joint policy. Please justify this connection and/or clarify the mechanisms by which agents' actions become correlated. From my understanding, InfoPG (with this architecture) would not cause the MI between the 3rd and 2nd piston to actually change over time in the BGP experiments -- that is, learning would not bring about any reduction in their MI as the main text describes.\n\n# Questions/Comments\n- It is hard to understand the aspects of InfoPG that set it apart from prior work. It may help to reconsider where MOA and PR2 are first detailed.\n- In the Section 3 paragraph about MI, you write: ```In our work, X and Y are policy distributions of two interacting agents.``` This is vague. Please be more clear about what the \"policy distributions\" are. I'm assuming it's the action distribution of each policy, but the paragraph is not very concrete.\n- Consider making it a bit more clear what \"InfoPG\" refers to. The k-level encoding/decoding policy definition? Something to do with the objective? Perhaps Section 4.3 is sufficiently clear, but just as a note I got a little bit confused about what \"InfoPG\" is meant to describe.\n- For the bottom row of Figure 2, how are you estimating MI? It would be good to state that in the paper. Also, what makes this an \"ablation\" study?", "summary_of_the_paper": "This work introduces InfoPG for learning coordination in fully decentralized multi-agent games. InfoPG models agent policies following *k*-level reasoning. The authors present a theoretical analysis to show that, under InfoPG, policy gradient optimizes a form of mutual information related to coordination. Empirical demonstrations show that InfoPG enables better performance than conceptually related baselines, with some demonstration of how InfoPG better adapts to a version of a Byzantine Generals Problem.", "summary_of_the_review": "My starting recommendation is: weak reject.\n\nI hope the authors can use the rebuttal period to correct any misunderstandings that may contribute to my lower score.\n\nHowever, assuming I have understood things accurately, I am primarily concerned with the notion that InfoPG is a genuinely decentralized approach. It seems to me that the policy is centralized because of how the communication policy works. I wonder how much the benefit of InfoPG simply comes from the fact that each agent naturally gets more information about the state of the world. More generally, I worry that the work misrepresents itself, using phrases like \"communication\" and \"*k*-level reasoning\" where they may not be appropriate. I am interested in how the authors defend these choices and characterizations.\n\nI also cannot escape the sense that the MI lens is somewhat *post hoc.* It may be possible to show that other MARL algorithms implicitly target MI, if it is indeed a corollary of coordination. Bottom line: a lot of the paper is spent on the theoretical connections between InfoPG and an abstract metric; I think that space would have been better spent on empirical analysis. Again, if I have overlooked the importance of (this form of) MI in these task settings, I hope the authors will correct me.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "K8Cr05RdmTY", "reviewer": "Reviewer_7nod", "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": "## Strong points\n\nI find it very innovative \n1. to reformulate the policy $p(.|s)$ to be $p(.|a^{j,k}, a^{i,{k-1}},  a^{i,{k-1}}, ...)$\n2. to use the K-level Bayesian tree to represent the interaction between agents.\n\nThe experiments are abundant\n\n## Issues\n1. Line 12 of Algorithm 1, how the MAP sample is carried out? For discrete actions, one can choose the max posterior action by enumeration, what about continuous actions?\n\n2. Line 19 of Algorithm 1: which equation does this correspond to?\nIn the explanation text, line 19 is not mentioned.\n\n3. What is $J(\\theta)$ exactly in Eqn (2) and (15)? Could you elaborate on that?\n\n4.  In Appendix A.5 Full proof of Theorem 1, page 17, paragraph between equation (35) and eqn. (36),  for a Bayesian tree, why\n  $\\sum_x \\sum_y p(x'|x,y)p(x,y|y')=p(x'|y')$?\n", "summary_of_the_paper": "The paper proposed  Info-PG, by reformulating the individual policy conditioned on state or partial observation to conditional on actions of other agents and with K-level rationalizability from cognitive hierarchy theory, the policy is conditioned recursively on lower levels of actions from all agents.\nThe optimization of the policy is in the same form of policy gradient algorithm.\nThe author showed that with reward shaping or applying relu on advantage, optimizing the reformulated policy is implicitly maximizing lower bound of mutual information across agents' policies.\nIn the case of Byzantine General's Problem where at least one agent is not cooperative, which could be detrimental to multi-agent learning, the author showed that by removing the relu on advantage, the policy gradient on the reformulated policy lead to tuning the upper bound of mutual information. The mutual information between the agent in question and the fraudulent agent will has its upper bound tuned down in case of negative reward, thus the fraudulent agent won't reduce the uncerntainty of policy of the agent in question, thus won't poison the multi-agent learning.\nThe algorithm is evaluated on a variety of multi-agent decentralized learning environments with promising results.\n\n", "summary_of_the_review": "In general the paper is innovative and solid, there are several issues as in the main review section that need to be addressed.", "strength_and_weaknesses": "", "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": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes a method for decentralized learning of cooperative games by maximizing the mutual information between the agents. The paper is novel and interesting and well evaluated.

Prior to the rebuttal, most of the reviewers saw presentation as the biggest weakness. Specifically, it was not clear what InfoPG refers to, and how it is related to the mutual information. During the rebuttal the authors cleaned up the misunderstandings around the presentation and provided a detailed analysis in the Appendix.

While the author responses provided helpful clarification and analysis, the authors should revise the paper holistically to remove unnecessary terminology and connections, and bring the analysis in the main text.
Decision: Accept (Poster)