# Effects of Spectral Normalization in Multi-Agent Reinforcement Learning
††thanks: Code Link: https://github.com/kinalmehta/epymarl_spectral/

Kinal Mehta  CSTAR
IIIT Hyderabad
Hyderabad, India
<EMAIL_ADDRESS>Anuj Mahajan  Department of Computer Science,
University of Oxford
Oxford, UK
<EMAIL_ADDRESS>Pawan Kumar  CSTAR
IIIT Hyderabad
Hyderabad, India
<EMAIL_ADDRESS>
###### Abstract

A reliable critic is central to on-policy actor-critic learning. But it
becomes challenging to learn a reliable critic in a multi-agent sparse reward
scenario due to two factors: 1) The joint action space grows exponentially
with the number of agents 2) This, combined with the reward sparseness and
environment noise, leads to large sample requirements for accurate learning.
We show that regularising the critic with spectral normalization (SN) enables
it to learn more robustly, even in multi-agent on-policy sparse reward
scenarios. Our experiments show that the regularised critic is quickly able to
learn from the sparse rewarding experience in the complex SMAC and RWARE
domains. These findings highlight the importance of regularisation in the
critic for stable learning.

###### Index Terms:

Spectral Normalization, MARL, Multi-Agent Reinforcement Learning, Optimization

##  I Introduction

Multi-agent reinforcement learning (MARL) framework [1] can be used to
formulate many real-world tasks in autonomous driving, robotics, etc. Having
multiple agents introduces several new challenges [2], which include
exponential growth in the joint action space, non-stationarity in the
environment due to co-evolving agents, exploration in the joint action space
[3, 4], credit assignment and gradient variance. Non-stationarity arising from
multi-agents is usually dealt with using a centralised training approach. But
dealing with all the challenges of exponential growth of the joint action
space remains an open problem. All these challenges, when combined with even a
little sparsity in rewards, make learning very difficult in MARL. The most
successful approach to decentralised cooperative MARL has been centralised
training decentralised execution (CTDE) [5]. Many value-based [3, 6, 7, 8] and
policy-based [9, 10] methods have been developed under the umbrella of CTDE.
The method Multi-agent PPO (MAPPO) [11] is a widely used on-policy MARL
algorithm which is able to match the performance of off-policy value-based
methods that have been shown to perform better on various environments.

Actor-critic algorithms have been successfully used in many single-agent [12]
and multi-agent [11, 10] reinforcement learning tasks. Critic is a central
part of the actor-critic framework, which evaluates the action produced by the
actor. The effectiveness of the actor depends on the effectiveness of the
critic; increasing the stability of the critic directly correlates to
increasing the actor’s effectiveness [13]. In this work, we focus on the
sparse rewards scenarios, which are often seen in real-world settings. We show
that the capability of MAPPO is hampered significantly in sparse reward
scenarios. To address this, we propose a critic regularisation technique
called Spectral Normalization that leads to better critic convergence which in
turn leads to better policy convergence. The generative adversarial networks
[14] are known to be notoriously difficult to train, and numerous methods have
been proposed [15, 16, 17]; it involves solving a delicate minmax optimization
problem. Spectral normalization has been used to stabilize the discriminator
in Generative Adversarial Networks (GANs) [18]. We hypothesize that by
introducing sparsity in the reward, critic learning gets affected and propose
to regularise critic with spectral normalization to aid the critic to learn.
Applying spectral normalization constraints the Lipschitz constant of the
layers.

We empirically study the effects of reward sparsity on critic learning in
MAPPO on two different cooperative multi-agent benchmarks: StarCraft multi-
agent challenge (SMAC) [19] and multi-robot warehouse (RWARE) [20]. We start
by comparing the performance of MAPPO with critic regularised MAPPO. We then
analyze the critic learning by comparing the logarithm of the gradient norms
of the critic of the two variants and show how applying spectral normalization
on the critic helps stabilize its gradients. Our results help us understand
the importance of critic learning in multi-agent scenarios under sparse
rewards.

Our contributions can be summarised as follows:

  * •

We introduce a sparse reward configuration for SMAC and show that it is
difficult to learn when compared to standard reward configuration.

  * •

We propose to regularise the critic with spectral normalization and show that
it helps learn better policies under sparse rewards.

  * •

We analyse the effects of applying spectral normalization and show that it
helps 1) stabilise the critic gradients and 2) has an optimization effect of
scaling the gradients of the entire critic by the product of the largest
spectral value of the weight matrices.

We start by introducing the multi-agent RL, PPO, MA-PPO and Spectral
Normalization in Section III followed by discussion on optimization effects of
Spectral Normalization in Section IV. After that we describe our experimental
setup in Section V and present our results and discussion in Section VI.

|
---|---
Figure 1: Illustration of an RWARE environment and a SMAC map

##  II Related Work

There has been considerable development in cooperative multi-agent
reinforcement learning in recent years[6, 21, 3, 11, 10]. Value-based as well
as policy-based CTDE-MARL algorithms are effective in cooperative tasks. But
these works do not focus on the sparse reward scenarios and mainly address
learning decentralized agents with factored value functions or policies.

Spectral Normalization has been used in GANs[18], as a regularizer which leads
to better sample efficiency [22] or to improve robustness of uncertainty
estimates [23]. In the context of RL, SN has been used in model-based RL in
uncertainty estimation [24] to enable deeper networks [13] and to also show
that SN regularised networks can compete with algorithmic innovations [25].
Tesseract [10] uses tensor decompositions to learn robust estimates for the
underlying MDP dynamics and action-value function with provable sample
efficiency in multi agent setting.

To the best of our knowledge, we are the first to apply SN in the context of
multi-agent RL. Our work differs from the previous works in the sense that we
show that SN can be used to make critic more robust to the noise induced by
sparse rewards under multi-agent scenarios. Previous works have shown that
adding SN to the value function estimator helps stabilize its learning by
stabilizing its gradients [13] as well as act as an update-step scheduler
[25]. In our work, we observe that applying SN in multi-agent scenarios leads
to both of these benefits.

##  III Background

###  III-A Cooperative MARL

We consider a fully cooperative multi-agent reinforcement learning task and
model it as a decentralized partially observable MDP (Dec-POMDP). Dec-POMDP
can be defined by tuple $\\{S,U,P,r,Z,O,n,\gamma\\},$ where $S$ is the state
space of the environment, and $z^{i}\in Z$ is the local observation of each
agent sampled according to the observation function
$O(s,i):S\times\mathcal{A}\rightarrow Z$. The action-observation history for
an agent $i$ is $\tau^{i}\in T\equiv(Z\times U)^{*}$, on which the policy
$\pi^{i}(u^{i}|\tau^{i}):T\times U\rightarrow[0,1]$ of each agent is
conditioned. At each time step $t$, every agent
$i\in\mathcal{A}\equiv\\{1,\,\dots,\,n\\}$ chooses an action $u^{i}\in U$ with
a decentralised policy $\pi^{i}(\cdot|\tau^{i})$ using only its local action-
observation history $\tau^{i}$. The agents jointly optimize the discounted
accumulated reward

$J=\mathbb{E}_{s_{t},\mathbf{u}_{t}}\left[\sum_{t}\gamma^{t}r(s,\mathbf{u})\right],$

where the joint action space $\mathbf{u}\in\mathbf{U}\equiv U^{n}$ can be
denoted as a tuple $\mathbf{u}=(u^{1},\dots,u^{n})$. When $n=1$ the problem
becomes a POMDP and is significantly easier to solve. Here
$P(s^{\prime}|s,\mathbf{u}):S\times\mathbf{U}\times S\rightarrow[0,1]$ is the
state transition function,
$r(s,\mathbf{u}):S\times\mathbf{U}\rightarrow\mathbb{R}$ is the reward
function shared by all agents and $\gamma\in[0,1)$ is the discount factor. The
state-value function conditioned on joint policy $\boldsymbol{\pi}$ is defined
as

$V^{\boldsymbol{\pi}}(s_{t})=\mathbb{E}_{\mathbf{u}\sim\boldsymbol{\pi}}\left[\sum_{k=0}^{\infty}\gamma^{k}r_{t+k}\,|\,\mathbf{s}\right].$

A collaborative team aims to learn an optimal joint policy
$\boldsymbol{\pi}=\Pi_{i=1}^{n}\pi^{i}$ which maximizes the accumulated reward
$J$.

###  III-B PPO and MA-PPO

PPO [12] is a single-agent actor-critic algorithm which optimizes the clipped
objective with a $KL$ penalty. The objective for policy optimization under PPO
is

$\mathbb{E}_{t}[\min(\rho_{t}(\theta)A_{t},\text{clip}(\rho_{t}(\theta),1-\epsilon,1+\epsilon)A_{t})-\beta\cdot
KL_{p}],$ (1)

where $A_{t}$ is the advantage for that given state $s_{t}$ and action
$u_{t}$, $\theta$ is the policy network weights, $\theta_{old}$ is the policy
network weights using which the action was selected,

$\rho_{t}(\theta)=\dfrac{\pi_{\theta}(u_{t}|s_{t})}{\pi_{\theta_{old}}(u_{t}|s_{t})}$

is the probability ratio of the selected action and

$KL_{p}=KL[\pi_{\theta_{old}}(\cdot|s_{t}),\pi_{\theta}(\cdot|s_{t})]$

is the $KL$ divergence between the old and the new policy distributions. The
advantage is calculated as follows.

$A_{t}(s_{t},u_{t})=r_{t}+\gamma\cdot
V^{\pi}_{\phi}(s_{t+1})-V^{\pi}_{\phi}(s_{t}),$ (2)

where $V_{\pi}$ is the value function or critic. The critic is trained to
minimise the following objective.

$\min_{\phi}\,[G_{t}-V^{\pi}_{\phi}(s_{t})]^{2}.$ (3)

Here, the training of the policy is driven by the value prediction accuracy
from the critic.

MAPPO [11] is a multi-agent extension of PPO where the critic is centralised
and has access to privileged information during the training. The centralised
critic learns the joint value function of the cooperative environment.

In a multi-agent scenario, the challenges of training critic are even more
severe due to an exponential blowup of the joint action space [10] and
potential non-stationarity of the environment. When using a central critic
with a CTDE framework, a single critic with the same set of parameters is
responsible for learning the value prediction for all the agents. This might
lead to conflicting goals for the critic leading to unstable critic updates.
This problem amplifies with the increase in number of agents.

As we mentioned earlier, the learning of policy depends on how accurate the
critic’s predictions of value estimates are. When we introduce one more
challenge of reward sparsity, the noise in critic learning is further
increased due to bootstrapping from an inaccurate critic. The problem of an
unstable critic is even more prominent when the rewards become sparse. In
complex scenarios like SMAC, this could also cause the actor-critic based
agents to not even find the optimal policy, which is reflected in our results
in Fig. 3. In a sparse reward setting, there is very little signal from the
environment to improve the value prediction and hence it becomes difficult for
the critic to learn the actual state-value function. Techniques like HER [26]
have been developed for off-policy learning.

###  III-C Spectral Normalization in Reinforcement Learning

Spectral normalization (SN) has been used to stabilise the discriminator
learning in GANs[27]. A function is $k-$Lipschitz continuous in $l_{2}$-norm
if

$\lVert f(x_{1})-f(x_{2})\rVert_{2}\leq k\lVert x_{1}-x_{2}\rVert_{2}.$ (4)

Considering a feed-forward layer, the Lipschitz constant of the layer is
defined as the largest singular value of the weight matrix of that layer.
Spectral normalization normalizes the weight matrix by its largest spectral
value, constraining that layer to be $1-$Lipschitz smooth.

$\hat{W}=\frac{W}{\lVert W\rVert}=\frac{W}{\sigma_{\max}(W)}.$ (5)

We can also control the smoothness of the function to be $k$ Lipschitz smooth
by adding an extra parameter $k$ which can be tuned.

$\hat{W}=\frac{W}{\operatorname{max}(\sigma_{\max}(W),k)}.$ (6)

The Lipschitz constant of a composite of two functions $f_{1}$ and $f_{2}$
with Lipschitz constant $k_{1}$ and $k_{2}$ will be bounded by $k_{1}\cdot
k_{2}$. Similarly the Lipschitz constant of a neural network can be bounded by
the product of Lipschitz constant of each layer. For more details on Lipschitz
constant of various layers and activation functions, we refer to [22].

We can draw parallels between GANs and actor-critic RL algorithms. Just as the
performance of the generator is driven by the accuracy of the discriminator,
in actor-critic, the performance of actor or policy is driven by the accuracy
of the critic. We use spectral normalization in the critic to stabilize its
gradients and learning. Using SN makes the critic updates more stable and
hence aids learning of the policy. In case of sparse rewards scenario, the
noise from the bootstrapped updated usually interferes with the actual reward
signal. SN helps mitigate this issue by constraining the layers to be
Lipschitz continuous and hence bounding the representation space.

As done in [18], the power iteration method is used to compute the largest
spectral value for applying spectral normalization. The additional computation
cost is relatively small compared to the full computational cost of the critic
network. The time comparisons when applying spectral normalization on GANs is
shown in [18].

|  |
---|---|---
Figure 2: Learning curves on RWARE comparing MAPPO and MidSN-MAPPO. As RWARE
is a relatively simple environment where explicit coordination is not
necessary, the final performance of both variants is almost the same. However,
we can observe that MidSN-MAPPO converges a bit faster.

##  IV Optimization effects of Spectral Normalization

Let us analyze the activation calculation of a feed-forward layer with and
without spectral normalization. The equation for a layer $i$ without spectral
normalization can be written as:

$\displaystyle z_{i}$ $\displaystyle=W_{i}a_{i-1}+b_{i}$ (7) $\displaystyle
a_{i}$ $\displaystyle=\operatorname{ReLU}(z_{i}),$ (8)

where $a_{0}\triangleq x$ is the input to the network.

Now let us look at the equations when we apply spectral normalization to a
feed-forward layer.

$\displaystyle\hat{z_{i}}$ $\displaystyle=\hat{W_{i}}a_{i-1}+b_{i}$ (9)
$\displaystyle\hat{a_{i}}$ $\displaystyle=\operatorname{ReLU}(\hat{z_{i}}),$
(10)

Here $\hat{W_{i}}=k_{i}^{-1}W_{i}$ is the weight matrix after applying
spectral normalization. Here $k_{i}$ is the largest singular value of the
weight matrix. Comparing the above equations, we can observe that only the
weight matrix is scaled using the largest singular value, whereas the bias is
unchanged. Due to this, the sign of the pre-activations $z$ is not preserved
($[z_{i}>0]\neq[\hat{z_{i}}>0]$). Hence we cannot write a direct relation
between $\frac{\partial\mathcal{L}}{\partial W_{i}}$ and
$\frac{\partial\hat{\mathcal{L}}}{\partial W_{i}}$

For simplicity of analysis let us consider the network without bias. So the
equation for a specific layer $i$ can be written as follows:

$\displaystyle z_{i}$ $\displaystyle=W_{i}a_{i-1}$ (11) $\displaystyle a_{i}$
$\displaystyle=\operatorname{ReLU}(z_{i}),$ (12)

where $a_{0}\triangleq x$ is the input to the network.

Let a subset of layer $\mathcal{S}\subseteq\\{1,2,\ldots,L\\}$ are spectral
normalized and are individually 1-Lipschitz continuous. The weight matrix of
the regularised layers can be defined as $\forall
i\in\mathcal{S}:\hat{W_{i}}=\langle k_{i}^{-1}\rangle W_{i}$ where
$k_{i}=\sigma_{\max}(W_{i})$ is the largest singular value of that weight
matrix. Here $\langle\cdot\rangle$ is the gradient stop operator and hence
back-propagation is not applied through the singular value calculations.

Now let us update the equations for the above described feed-forward network
when applying spectral normalization to it.

$\hat{z}_{i}=k_{i}^{-1}W_{i}\hat{a}_{i-1}$ (13)
$\hat{a}_{i}=\operatorname{ReLU}(\hat{z}_{i}),$ (14)

where $k_{i:j}^{-1}\triangleq\prod_{i\leq l\leq j\wedge
l\in\mathcal{S}}k_{l}^{-1}$. We can write eq. 13 in terms of non-regularised
activation as follows

$\hat{z}_{i}=k_{1:i}^{-1}W_{i}{a}_{i-1}.$ (15)

The above equation is valid as spectral normalization is scaling operation and
hence the sign of the activation will be preserved
($[a_{i}>0]=[\hat{a}_{i}>0]$).

The loss is calculated on the final layer of the network and hence can be
written as $\mathcal{L}\triangleq\operatorname{loss}(z_{L})$. The loss
calculation for the regularised network will be updated to
$\hat{\mathcal{L}}\triangleq\operatorname{loss}(\hat{z}_{L})=\operatorname{loss}(k_{1:L}^{-1}z_{L})$.

$\displaystyle\operatorname{MLP}$ $\displaystyle\operatorname{SN-MLP}$ (16)
$\displaystyle\mathcal{L}$ $\displaystyle\triangleq\operatorname{loss}(z_{L})$
$\displaystyle\hat{\mathcal{L}}$
$\displaystyle\triangleq\operatorname{loss}(\hat{z}_{L})$ (17)
$\displaystyle\frac{\partial\mathcal{L}}{\partial W_{i}}$
$\displaystyle=J_{i}{\delta}_{L}a_{i-1}^{T}$
$\displaystyle\frac{\partial\hat{\mathcal{L}}}{\partial W_{i}}$
$\displaystyle=k^{-1}J_{i}\hat{\delta}_{L}\hat{a}_{i-1}^{T},$ (18)

where $k^{-1}=\Pi_{i\in\mathcal{S}}k_{i}^{-1}$,
$\delta_{L}\triangleq\frac{\partial\mathcal{L}}{\partial z_{L}}$ is the
Jacobian w.r.t. the network’s output and similarly
$\hat{\delta}_{L}\triangleq\frac{\partial\hat{\mathcal{L}}}{\partial\hat{z}_{L}}$
is the Jacobian with respect to the regularised network’s output and

$J_{i}\triangleq\Pi_{j=i}^{L-1}[\operatorname{diag}([z_{j}]>0)W_{j+1}^{T}].$

Based on the above equations, it is evident that applying spectral
normalization leads to gradient scaling by $k^{-1}$. This shows that the
optimization step of the regularised network is scheduled based on the product
of largest spectral values of the normalized layers. For detailed analysis of
how spectral normalization effects various layers, activation and the bias
terms, we refer to [25, 22]. We also note here that spectral normalization is
a form of preconditioning [28, 29, 30, 31, 32, 33, 34, 35, 36].

Under sparse rewards, the learning of the critic is unstable as it uses
bootstrapped targets from an untrained critic. This could lead to
unpredictable updates in the weight matrices. When regularizing the critic
with SN, the gradient scaling with $k^{-1}$ restricts the model weights from
diverging due to incorrect target estimates. While once the critic is trained
a bit, it leads to more accurate and consistent bootstrapped targets.

|  |
---|---|---
Figure 3: Average battles won on various SMAC maps averaged across several
seeds. SMAC is a very challenging benchmark where each map requires a specific
skill to be acquired to win. We observe that LastSN-MAPPO shows much better
and more stable final performance than MAPPO when evaluating under sparse
reward configuration. However, the results on Corridor are a bit surprising.
We talk about that in more detail in Section VI-B

##  V Experimental Setup

We use MAPPO as our on-policy multi-agent algorithm to perform all the
evaluations. Implementation and configuration from [20] are used for all our
experiments. The actor consists of $3$ layers with GRU as the middle layer,
and the critic uses $3$ layered feed-forward network. All the layers have $64$
neurons, and the hidden dimension of GRU is $64$. Adam [37] optimizer with a
learning rate of $5\times 10^{-4}$ is used for updating the network weights.
Gradient clipping is applied to both the actor and critic gradients with a
gradient norm $10$. The weights of the actor and critic are shared across all
agents[11].

For learning the critic we use 10-step temporal difference learning rule. The
actor is optimized using the standard PPO objective. We normalize the returns
for critic for two of our variants, FullSN-MAPPO and LastSN-MAPPO.

We test three different variants with spectral normalization on critic and a
standard MAPPO:

  * •

_FullSN-MAPPO_ : Spectral Normalization (SN) is applied on all critic layers.

  * •

_MidSN-MAPPO_ : SN only applied on the second layer or the middle layer of the
critic.

  * •

_LastSN-MAPPO_ : SN applied to the final layer of the critic.

  * •

_MAPPO_ : Standard MAPPO implementation with no spectral normalization.

##  VI Results

We empirically evaluate our results on two cooperative multi-agent benchmarks,
multi-robot warehouse (RWARE) and starcraft multi-agent challenge (SMAC). We
report our scores averaged across four seeds.

###  VI-A RWARE Environment

RWARE is a partially observable sparse reward benchmark introduced in [20]. It
is a grid-world environment where the agents are rewarded for delivering the
requested shelf from the warehouse. Agents can only observe a $3\times 3$ grid
surrounding themselves. We consider three different tasks which vary the grid
size and the number of agents. This is a relatively simpler environment where
a single agent can complete the task without any help from the other agents in
the environment. This reflects in our results in Fig. 2 where two variants,
MAPPO and MidSN-MAPPO, show similar final performance, with MidSN-MAPPO being
quicker to converge.

We compare three different RWARE environments with a varying number of agents
and environment sizes.

  * •

_tiny-2ag_ is the smallest map with two agents. We observe that the spectral
normalized variant converges a bit faster comparatively.

  * •

_tiny-4ag_ is the same as the previous map but with four agents. In this case,
we do not see any significant difference between the two variants. Though our
variant with normalized critic seems to converge a bit faster again.

  * •

_small-2ag_ is a larger map with almost double the number of shelves in the
environment with only two agents.

Overall in all three environments, we observe our variant to converge early,
but the final performance is almost the same.

Figure 4: Comparing dead enemies through the training shows that MidSN-MAPPO
is always ahead of MAPPO even though the final win rate is the same for the
two variants, MidSN-MAPPO is able to kill more enemies even in the battles
which are not a conclusive win.

Figure 5: Gradient norm of the critic throughout the training. Even though
MidSN-MAPPO shows improvement over MAPPO in both the environments, the reason
for this performance gain is different in the two maps. In _27m_vs_30m_ , the
critic gradients are stable for both the variants, still MidSN-MAPPO is
better. In this case, the performance gain can be attributed to the
optimization effects of SN on the critic. While in _corridor_ , SN helps
stabilise the critic gradients, directly correlating to overall performance
gain.

###  VI-B SMAC Environment

SMAC is a benchmark based on the Starcraft II game. This environment consists
of battle scenarios where a team of agents is controlled to defeat the enemy
team, which uses fixed policies. This is also a partially observable
environment where each agent only observes a fixed around itself for other
agents. Here too, we consider three different tasks with a varying number of
agents and unit types. The primary challenge in these tasks is learning
optimal behaviour under partial observability and the large joint action space
growing based on the number of agents. As we specifically wanted to evaluate
the performance on sparse rewards, we propose a custom reward configuration
where the agents are awarded rewards only in cases of death and win/loss. For
each death in the ally team, a reward of $-10$ is awarded, and for each kill
in the enemy team, a reward of $+10$ is awarded. Along with the death reward,
a reward of $+200$ is awarded for winning the battle, killing all the enemy
units, and similarly, a reward of $-200$ is awarded if all the units in the
ally team die. We do not use rewards based on health loss due to attacks which
are usually used.

We consider three super-hard scenarios from Starcraft Multi-Agent Challenge
(SMAC) for our comparisons. Each scenario evaluates different aspects of the
environment. _3s5z_vs_3s6z_ helps us evaluate the performance of imbalanced
teams. We can observe that variants with spectral normalized critic gain
significant performance compared to the standard critic variant. _27m_vs_30m_
has the largest ally team of 27 marines. In this scenario as well, we observe
that our variant performs significantly better. This shows that our method can
scale to a large number of agents. Even though spectral normalization
constraints the critic, the shared weights can learn representation for many
agents. _corridor_ requires effective use of terrain features and block the
choke point to avoid attacks from different directions. Subtle tactics like
blocking the choke point to avoid attack from different directions as there is
a considerable imbalance in the team since six friendly Zealots face 24 enemy
Zerglings. All variants find it challenging to solve this environment
consistently under sparse rewards. But still, the convergence of MidSN-MAPPO
with normalized critic is quick compared to the standard variant. When we
compare the number of dead enemies in Fig. 4, we can see that MidSN-MAPPO is
performing relatively better. Even though both the algorithms fail to have
high win-rates due to slow regenerative ability of enemy Zerglings, which
makes it difficult to kill them unless attacked continuously, we observe that
MidSN-MAPPO is able to kill more enemies than MAPPO.

Fig. 3 compares the win rate on different SMAC scenarios under sparse rewards.
We can observe that all three SN variants perform better than the normal MAPPO
on _3s5z_vs_3s6z_ and _27m_vs_30m_. LastSN-MAPPO achieves the best final win-
rate consistently across various seeds. This shows that regularizing the
critic with spectral normalization does indeed help to learn under sparse
reward scenarios. However, the results on _corridor_ paint a different
picture. We observe that both the variants where SN is applied on the last
layer of the critic underperform compared to the other two scenarios.

Applying SN on the last layer of critic causes its output to be smooth [25].
However, the value function doesn’t need to be smooth. That is, when the focal
agent has more health and the enemy agent has relatively less health, the
return will be highly positive, but just a slight difference in the health of
the two agents leading to an enemy agent having higher health would lead to
highly negative reward. The scenarios _3s5z_vs_3s6z_ and _27m_vs_30m_ where
FullSN-MAPPO and LastSN-MAPPO perform well have open maps and there is a lot
of place for the agents to move around. Hence the value function would be
smooth. However, in _corridor_ , there are choke points that constraint the
movements of the agents. This leads to non-smooth value function, which
ultimately causes the failure of FullSN-MAPPO and LastSN-MAPPO on this
scenario. It would be safe to conclude that applying SN on the final layer
only helps when the value function is smooth. Otherwise, we have to restrict
ourselves to not apply SN on the final layer of the critic.

To understand more about the effects of normalizing critic, we analyze the
norm of the gradients of critic. Fig. 5 compares the gradient norm on two SMAC
scenarios, _27m_vs_30m_ and _corridor_. We observe that learning happens in
both the maps, but there is a critic gradient explosion in the normal variant
on _corridor_. Notice that the plots are in $\log$ scale. This shows that
regularising critic with spectral norm helps stabilize the learning in critic
by stabilizing its gradients.

But another question that remains is what exactly causes the performance gain
in _27m_vs_30m_? As we observe, the gradient norm of both variants is almost
in the same range. The performance gain, even when the gradient norm is not
exploding, can be explained based on the effects of SN discussed in section
IV. Let’s look at the output and gradient equations of a three-layered fully-
connected network. We observe that applying spectral normalization on a layer
is equivalent to scaling the gradients of the complete network by the inverse
of maximum spectral value $\rho^{-1}$. This scaling of the gradient effect
acts as a step-size scheduler based on the spectral values of the regularised
layers. Hence the performance gain in _27m_vs_30m_ can be attributed to the
gradient scaling effect of SN.

We can conclude from the above analysis that the benefits of applying spectral
normalization to the critic are as follows

  1. 1.

Stabilise critic by constraining the gradients

  2. 2.

Optimization effect by scaling the gradient by the inverse of the maximum
spectral value

  3. 3.

Better learning of smooth value functions by applying SN on the last critic
layer

However, it is important to note that even though SN can help in stabilizing
the critic learning, it can only help up to an extent and under the conditions
that the agent is able to reach some rewarding state by random exploration. In
case of extremely sparse rewards, e.g., only win/loss reward in SMAC, it is
extremely unlikely that the team of agents randomly stumbles upon a winning
situation. As there is a very slim chance of getting an actual positive
reward, there is no information presented to the critic that it can leverage.
Hence stable critic helps only under the condition that the agent is able to
reach rewarding states, but the reward signal might get suppressed by the
noise from the untrained critic.

##  VII Conclusion and Future Work

We have investigated the challenges of sparse rewards in multi-agent
environments and have empirically shown that regularising the critic with
Spectral Normalization helps to learn a better policy. We show that in multi-
agent sparse rewards scenarios, the benefits of applying SN are two folds, it
restricts the irregularities in critic and stabilizes its gradients, and also
changes the optimization dynamics by gradient scaling of the entire network.
It is crucial to consider the smoothness of the value function of the
environment when applying SN to the critic. Applying SN on the final layer of
the critic when the value function is non-smooth hurts the performance. These
observations highlight the importance of stable critic in MARL and show how SN
can improve critic learning under challenging conditions.

As a future work, it would be interesting to explore the effects of spectral
normalization when used on the actor network and using a deeper critic
network. Moreover, our experiments were only limited to cooperative
environments. Knowing how constraining the network with spectral normalization
affects learning in general-sum games would give us more insight into its
benefits in more general MARL settings. Additionally, we would also like to
explore further the analytic relation between sample efficiency in RL [38] and
the degree of spectral norm applied.

## Acknowledgement

This work was carried out under RIPPLE funding at the International Institute
of Information Technology, Hyderabad, India. We thank the host institute for
providing compute resources for an extended period of time, and for HPC
resources funded under the RIPPLE grant.

## References

  * [1] K. Mehta, A. Mahajan, and P. Kumar, “marl-jax: Multi-agent reinforcement leaning framework for social generalization,” 2023. [Online]. Available: https://arxiv.org/abs/2303.13808
  * [2] A. Mahajan, M. Samvelyan, T. Gupta, B. Ellis, M. Sun, T. Rocktäschel, and S. Whiteson, “Generalization in cooperative multi-agent systems,” _arXiv preprint arXiv:2202.00104_ , 2022.
  * [3] A. Mahajan, T. Rashid, M. Samvelyan, and S. Whiteson, “Maven: Multi-agent variational exploration,” in _NeurIPS_ , 2019, pp. 7611–7622.
  * [4] T. Gupta, A. Mahajan, B. Peng, W. Böhmer, and S. Whiteson, “Uneven: Universal value exploration for multi-agent reinforcement learning,” _arXiv:2010.02974_ , 2020.
  * [5] R. Lowe, Y. Wu, A. Tamar, J. Harb, O. P. Abbeel, and I. Mordatch, “Multi-agent actor-critic for mixed cooperative-competitive environments,” in _NeurIPS_ , 2017, pp. 6379–6390.
  * [6] T. Rashid, M. Samvelyan, C. S. de Witt, G. Farquhar, J. Foerster, and S. Whiteson, “Qmix: Monotonic value function factorisation for deep multi-agent reinforcement learning,” 2018. [Online]. Available: https://arxiv.org/abs/1803.11485
  * [7] K. Son, D. Kim, W. J. Kang, D. E. Hostallero, and Y. Yi, “Qtran: Learning to factorize with transformation for cooperative multi-agent reinforcement learning,” _arXiv:1905.05408_ , 2019.
  * [8] T. Wang, T. Gupta, A. Mahajan, B. Peng, S. Whiteson, and C. Zhang, “Rode: Learning roles to decompose multi-agent tasks,” _arXiv:2010.01523_ , 2020\.
  * [9] C. Yu, A. Velu, E. Vinitsky, Y. Wang, A. Bayen, and Y. Wu, “The surprising effectiveness of ppo in cooperative, multi-agent games,” 2021.
  * [10] A. Mahajan, M. Samvelyan, L. Mao, V. Makoviychuk, A. Garg, J. Kossaifi, S. Whiteson, Y. Zhu, and A. Anandkumar, “Tesseract: Tensorised actors for multi-agent reinforcement learning,” in _ICML_ , vol. 139. PMLR, 2021, pp. 7301–7312.
  * [11] C. Yu, A. Velu, E. Vinitsky, J. Gao, Y. Wang, A. Bayen, and Y. Wu, “The Surprising Effectiveness of PPO in Cooperative Multi-Agent Games,” 2022. [Online]. Available: https://openreview.net/forum?id=YVXaxB6L2Pl
  * [12] J. Schulman, F. Wolski, P. Dhariwal, A. Radford, and O. Klimov, “Proximal Policy Optimization Algorithms,” 2017. [Online]. Available: http://arxiv.org/abs/1707.06347
  * [13] J. Bjorck, C. P. Gomes, and K. Q. Weinberger, “Towards Deeper Deep Reinforcement Learning with Spectral Normalization,” 2022. [Online]. Available: http://arxiv.org/abs/2106.01151
  * [14] I. Goodfellow, J. Pouget-Abadie, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville, and Y. Bengio, “Generative adversarial nets,” in _NeurIPS_ , vol. 27, 2014.
  * [15] F. Schaefer and A. Anandkumar, “Competitive gradient descent,” in _NeurIPS_ , H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, Eds., vol. 32. Curran Associates, Inc., 2019\.
  * [16] L. Mescheder, S. Nowozin, and A. Geiger, “The numerics of gans,” in _NeurIPS_ , ser. NIPS’17, Red Hook, NY, USA, 2017, p. 1823–1833.
  * [17] S. K. Danisetty, S. R. Mylaram, and P. Kumar, “Adaptive consensus optimization method for gans.” IJCNN, 2023.
  * [18] T. Miyato, T. Kataoka, M. Koyama, and Y. Yoshida, “Spectral normalization for generative adversarial networks,” in _International Conference on Learning Representations_ , 2018. [Online]. Available: https://openreview.net/forum?id=B1QRgziT-
  * [19] M. Samvelyan, T. Rashid, C. S. de Witt, G. Farquhar, N. Nardelli, T. G. Rudner, C.-M. Hung, P. H. Torr, J. Foerster, and S. Whiteson, “The StarCraft multi-agent challenge,” vol. 4. International Foundation for Autonomous Agents and Multiagent Systems, 2019.
  * [20] G. Papoudakis, F. Christianos, L. Schäfer, and S. V. Albrecht, “Benchmarking Multi-Agent Deep Reinforcement Learning Algorithms in Cooperative Tasks,” 2021. [Online]. Available: http://arxiv.org/abs/2006.07869
  * [21] P. Sunehag, G. Lever, A. Gruslys, W. M. Czarnecki, V. Zambaldi, M. Jaderberg, M. Lanctot, N. Sonnerat, J. Z. Leibo, K. Tuyls, and T. Graepel, “Value-Decomposition Networks For Cooperative Multi-Agent Learning,” _arXiv:1706.05296_ , 2017.
  * [22] H. Gouk, E. Frank, B. Pfahringer, and M. J. Cree, “Regularisation of Neural Networks by Enforcing Lipschitz Continuity,” 2020. [Online]. Available: http://arxiv.org/abs/1804.04368
  * [23] J. Z. Liu, Z. Lin, S. Padhy, D. Tran, T. Bedrax-Weiss, and B. Lakshminarayanan, “Simple and Principled Uncertainty Estimation with Deterministic Deep Learning via Distance Awareness,” 2020. [Online]. Available: http://arxiv.org/abs/2006.10108
  * [24] T. Yu, G. Thomas, L. Yu, S. Ermon, J. Zou, S. Levine, C. Finn, and T. Ma, “MOPO: Model-based Offline Policy Optimization,” 2020. [Online]. Available: http://arxiv.org/abs/2005.13239
  * [25] F. Gogianu, T. Berariu, M. Rosca, C. Clopath, L. Busoniu, and R. Pascanu, “Spectral Normalisation for Deep Reinforcement Learning: An Optimisation Perspective,” 2021.
  * [26] M. Andrychowicz, D. Crow, A. Ray, J. Schneider, R. Fong, P. Welinder, B. McGrew, J. Tobin, O. P. Abbeel, and W. Zaremba, “Hindsight Experience Replay,” _arXiv:2010.01523_.
  * [27] T. Miyato, T. Kataoka, M. Koyama, and Y. Yoshida, “Spectral Normalization for Generative Adversarial Networks,” in _ICLR_ , 2022.
  * [28] D. E. Carlson, E. Collins, Y.-P. Hsieh, L. Carin, and V. Cevher, “Preconditioned spectral descent for deep learning,” in _NeurIPS_ , vol. 28, 2015.
  * [29] S. Katyan, S. Das, and P. Kumar, “Two-grid preconditioned solver for bundle adjustment,” in _WACV_ , 2020, pp. 3588–3595.
  * [30] S. Das, S. Katyan, and P. Kumar, “A deflation based fast and robust preconditioner for bundle adjustment,” in _WACV_ , January 2021, pp. 1782–1789.
  * [31] ——, “Domain decomposition based preconditioned solver for bundle adjustment,” in _Computer Vision, Pattern Recognition, Image Processing, and Graphics_ , 2020.
  * [32] P. Kumar, K. Meerbergen, and D. Roose, “Multi-threaded nested filtering factorization preconditioner,” in _Applied Parallel and Scientific Computing_ , vol. 7782, Springer. Springer, Berlin, Heidelberg, 2013, pp. 220–234.
  * [33] P. Kumar, “Aggregation based on graph matching and inexact coarse grid solve for algebraic two grid,” _International Journal of Computer Mathematics_ , vol. 91, no. 5, pp. 1061–1081, 2014.
  * [34] P. Kumar, L. Grigori, F. Nataf, and Q. Niu, “On relaxed nested factorization and combination preconditioning,” _International Journal of Computer Mathematics_ , vol. 93, no. 1, pp. 179–199, 2016.
  * [35] C. Li, C. Chen, D. Carlson, and L. Carin, “Preconditioned stochastic gradient langevin dynamics for deep neural networks,” 2015.
  * [36] Y. Qiao, B. P. F. Lelieveldt, and M. Staring, “An efficient preconditioner for stochastic gradient descent optimization of image registration,” _IEEE Transactions on Medical Imaging_ , vol. 38, no. 10, pp. 2314–2325, 2019.
  * [37] D. P. Kingma and J. Ba, “Adam: A Method for Stochastic Optimization,” 2017\. [Online]. Available: http://arxiv.org/abs/1412.6980
  * [38] A. Mahajan and T. Tulabandhula, “Symmetry learning for function approximation in reinforcement learning,” _arXiv preprint arXiv:1706.02999_ , 2017.


# Collective Memory, Consensus, and Learning explained by Network Connectivity

Jeroen Bruggeman Department of Sociology, University of Amsterdam, Nieuwe
Achtergracht 166, 1018 WV Amsterdam, the Netherlands. Email:
<EMAIL_ADDRESS>
###### Abstract

Humans cluster in social groups where they discuss their shared past,
problems, and potential solutions, learn collectively when they repeat
activities, synchronize when they sing or dance together, and bond through
social cohesion. By representing a group network by a Laplacian matrix, the
outcomes of these activities, as well as group’s cohesion, can be predicted by
its second smallest eigenvalue, called algebraic connectivity. It predicts
well when processes converge towards a consensus or focal activity, but it
cannot predict divergence, such as division of labor or polarization.

Humans live in social groups, which yield advantages and disadvantages.
Advantages are access to information and collective goods, but they come at a
cost, including the maintenance of social ties, and there are risks of
exploitation and misinformation. In this paper, I focus on the social network
structure underlying a number of these advantages and disadvantages, most of
which have been examined separately in different fields. The network’s crucial
characteristic turns out to be its algebraic connectivity [1], which
interconnects, and provides new insights in, previously unrelated findings
about group learning [2, 3], collective memory [4, 5], agreement [6, 7, 8],
synchronization [9, 10], and social cohesion [11]. To see how, we will revisit
a number of experiments.

## Results

Experimental studies of communicating individuals have focused on different
kinds of shared information, such as memories [4, 5], network node coloring
[6], conventions [7], opinions [12, 13], and visual cues of body movement
[14]. In all these experiments, it turned out that pairwise differences
between individuals’ memories, opinions, ideas, and movements decreased, which
is also at the heart of the contact hypothesis [15].

Convergence in a group can be modeled as a grand total of decreasing pairwise
differences. Formally, when individuals $i$ and $j$ discuss their positions on
a given issue, $y$, their difference is $y_{j}-y_{i}$. Using matrix notation,
the process towards group consensus in a network, based on these pairwise
differences, can be written as

$\frac{d\mathbf{y}}{dt}=-\mathbf{L}\mathbf{y},$ (1)

where $\bf{L}$ is the network Laplacian (see Methods) and $\bf{y}$ a vector of
individuals’ positions [16]. So far, this is just an efficient notation for
well-known and well-replicated social influence models [17, 18]. The added
value is in the eigenvalue spectrum of $\mathbf{L}$. For initial opinions
$\bf{y}_{0}$ at $t_{0}$, the speed of convergence decreases with initial
opinions’ diversity, but increases with the second-smallest eigenvalue of the
Laplacian [16], denoted $\lambda_{2}$ and called _algebraic connectivity_ [1].
This also holds true for synchronization of connected oscillators [9], for
example singing or dancing individuals [10], even though models of
synchronization are different [19]. Algebraic connectivity is maximal for
fully connected networks, zero for networks with disconnected parts, and close
to zero if the network is very sparse in between denser parts [20] such as
social groups, for example Fig. 1b.

Figure 1: Two networks with the same size and density, used in a mnemonic
convergence experiment (adapted from Coman et al. 2016). (a) Network with
$\lambda_{2}=0.333$. (b) Network with $\lambda_{2}=0.074$. (c) Memory, or
opinion, convergence in network a (continuous lines) and network b (dotted
lines) according to the Laplacian model (Eq. 1).

The two networks in Fig. 1 were used in an experiment [4] that drew quite some
attention [21]. Subjects conversed about their past (i.e., a story made up by
the researchers that subjects first had to memorize) for a certain amount of
time. The authors concluded that in the network with more mnemonic alignment,
in Fig. 1a, clustering is lower and average distance (hops through the net)
smaller than in Fig. 1b. Their conclusions are correct, but the Laplacian
model (Eq. 1; Fig. 1c) contributes an explanation of the group dynamics,
namely how the group outcome emerges from interacting individuals. The model
also makes it possible to relate specific findings, such as this, to numerous
others. The first that comes to mind is a variation of the memory experiment,
where different ties were used over time [22]. In this variant, there were
four clusters with four subjects in each, with connections between the
clusters. If inter-cluster communication precedes within-cluster
communication, there is more convergence of memories than if the sequence is
reversed. Although algebraic connectivity cannot distinguish the two
treatments, because the same network is used in both, the Laplacian model,
solved numerically over subsequent rounds, predicts the experimental outcome.
Again, the model contributes precision and explanatory power to the authors’
positing that communication through bridging ties early on facilitates
mnemonic convergence. Furthermore, the explanatory power of the Laplacian
model, with or without its algebraic connectivity, turns out to be robust; its
predictions are impaired neither by asynchronous (versus simultaneous)
interactions nor by categorical (versus continuous) issues, where differences
$y_{j}-y_{i}$ are, strictly speaking, undefined.

Another experiment with categories was the formation of a convention among
multiple alternatives proposed by the subjects [7]. Subjects interacted over
30 rounds, communicating with one alter in each round. Three networks were
compared, each with $n=24$: a circular lattice where everyone had four ties
($\lambda_{2}=0.084$); a random network where everyone had four ties on
average ($\lambda_{2}=0.256$); and a network where subjects were connected to
a next alter in every subsequent round, homogeneously spread across the
network. In the latter network, this procedure resulted in a clique (fully
connected network) at round 23 ($\lambda_{2}=1.043$), when everyone had
interacted with everyone else. In the two networks with low connectivity
(lattice and random), a group convention was never achieved in time, in
contrast to the clique, where it always was.

Along with predicting experimental outcomes, algebraic connectivity can also
be used to measure social cohesion, to be regarded as the network structure
that bonds a group together and facilitates information transmission [23].
Because information transmitted over longer distances tends to deteriorate
[12, 24] or not arrives at all [25], it is important for group members that
distances to their sources are short, and there is network redundancy such
that a noisy or biased message through one path (concatenation of ties) can be
corrected by messages through other, non-overlapping, paths [11], as in Fig.
1a. Algebraic connectivity is larger in networks with shorter distances and
multiple non-overlapping paths (Methods). It is also larger when chords cross-
connect these paths, an aspect of redundancy that has been largely overlooked
in the literature, whereas they turned out to be crucial for reliable
transmission in an experiment with long paths [24]. Network redundancy and
proximity increase the robustness of a network, which, together with rapid
consensus on important issues, and interaction rituals [26] such as
synchronous singing and dancing [27], contribute to the bonding of a group,
and facilitate collective action [28]. Note that in general, algebraic
connectivity is only loosely related to density, because sparse connections
between (sub)groups strongly weaken the effect of increasing density within
(sub)groups, even though adding ties to a network cannot decrease algebraic
connectivity [29]. Therefore, assessing the algebraic connectivity of
(sub)groups is in most cases more informative than of a large network, which
will be very small or zero.

In more cohesive groups, not only convergence to consensus proceeds faster,
but also collective production of goods, such as building a house. Collective
production follows the learning curve [3]: the time it takes for a group to
finish an activity, $t$, decreases at a decreasing rate with the number of
times, $x$, the activity has been executed in the past. The functional form
often used is a power law [2], $t=ax^{b}$, with $b<0$. Due to repetition, a
group network becomes more efficient through individuals finding shortcuts in
their social “problem space” [30] with increasing probability [31], connecting
to knowledgeable colleagues at closer network distances. It has been proven
mathematically that this probabilistic tie relaying (keeping density fixed)
results in the learning curve [31, 32]. To see how algebraic connectivity
comes into play, we revisit an experiment wherein every subject was randomly
assigned an initial color, and was instructed to synchronize their color with
their network neighbors [6]. (The number of colors to choose from was the
chromatic number.) The time it took to achieve one overall color (i.e.,
consensus), $t$ seconds, was measured in six networks, all with the same
density and 36 subjects. The first had six densely connected clusters with one
tie connecting each cluster to the next; the remainder five networks were
obtained by randomly rewiring the ties of the first network with increasing
probability, $q\in\\{0,0.1,0.2,0.4,0.6,1\\}$, while keeping the, progressively
sparser, clusters connected to each other. In contrast to teams and business
companies [2], where individuals find shortcuts in their network by
themselves, the shortcuts in the coloring experiment were implemented by the
researchers. This difference set apart, the sequence of treatments was
network-wise identical to a sequence of snapshots of a learning process.
Bearing this in mind, thus writing $\lambda_{2}$ instead of $x$ to capture the
effect of network shortcuts, a learning curve is fitted to the data from the
coloring experiment (Fig. 2; $b=-0.434;p=0.0004;n=6$). The parameter is close
to the average in industry ($b\approx-1/3$) [2]. The learning curve predicts
the data much better than authors’ model with a concave, instead of convex,
curve.

Figure 2: Time to reach consensus as a function of the algebraic connectivity
of the network (data from Kearns et al. 2010). Note that the data was obtained
for given chances of random tie relaying, but here, pertaining levels of
algebraic connectivity are plotted.

## Discussion

An important lesson from the coloring experiment is that the incremental
effect size of algebraic connectivity is large at low levels, whereas further
increasing connectivity to higher levels has small effects. In other words, to
get most of the advantages of learning, a modest level of connectivity will
do. This aligns with other studies, where the effect of messages through
multiple ties was examined. In one of these studies, the chance to win
subjects over to accept a health improving behavior increased with the number
of ties through which they received health messages, but at a decreasing rate,
and more than three ties had no significant effect over and above three ties
[33]. The only exception we encountered was the presence of a time limit, when
a group result had to be achieved in a short period of time, in the convention
experiment [7].

Along with diminishing advantages, there are increasing disadvantages. If
people too easily converge to the majority, the result is not necessarily a
wisdom of the crowd but oftentimes a form of groupthink: a commitment to an
inferior solution to a given problem [34], a lack of innovation due to
cultural homogeneity [35], a memory of events that never happened [4], the
adoption of a conspiracy theory [36], or the punishment of critics with
valuable feedback [37]. For information from multiple sources to be
advantageous, two conditions must be fulfilled. First, people in the know
should not let themselves be influenced by sources with inferior information
[38, 39] (Eq.4 in Methods). Second, the least knowledgeable individuals should
either be aware that they can learn from their average social environment [39]
or specifically know which sources are best, and relay their ties accordingly
[38]. Both conditions are easier met at modest levels of algebraic
connectivity and density, when the network is not too efficient and social
pressure is not too strong.

In sum, most of the benefits of algebraic connectivity can be had at
relatively low levels, whereas further increasing connectivity by means of
extra ties entails costly tie maintenance, increasing information overload,
and higher risks of groupthink, while rarely yielding additional benefits. A
challenge for future studies is to determine the sweet spot.

In this paper, we have seen that the Laplacian model with its algebraic
connectivity predicts outcomes of various processes that converge.
(Mathematical conditions for convergence are in [8].) However, it cannot
predict divergence, for example choosing a color differing from one’s
neighbors [40], or division of labor in general. Nor can it predict when a
discussion about a controversial issue leads to polarization instead of
convergence [41, 42, 43], or how conflicts evolve in general. Furthermore,
there are challenges to social groups beyond convergence/divergence, for
example finding solutions to complex problems [44], for which algebraic
connectivity has limited use. Nonetheless, a Laplacian network representation
of social groups interconnects numerous findings from multiple fields, and
improves their explanations. It is also practical; if your meetings last too
long, increase their algebraic connectivity!

## Methods

### Laplacian matrix

In a set of $n$ individuals, indexed $i$ and $j$, their social ties are
denoted $a_{ij}\geq 0$. If $i$ pays attention to $j$, tie $a_{ij}>0$, and the
social influence by all others on $i$’s position on issue $y$ are written as
the sum total of pairwise differences [18],
$\sum_{j=1}^{n}a_{ij}(y_{j}-y_{i})$. To write this for everyone in one stroke
(Eq. 1), a Laplacian matrix is used

$\mathbf{L}=\mathbf{D}-\mathbf{A},$ (2)

with $\mathbf{A}$ the adjacency matrix of the network. $\mathbf{D}$ is a
diagonal matrix with $d_{ii}=\sum_{j}a_{ij}$ and $d_{ij}=0$ if $i\neq j$ [45].
The definition of $\mathbf{L}$ implies that its smallest eigenvalue
$\lambda_{1}=0$.

Results are most straightforward if $\mathbf{A}$ is binary and symmetric
($a_{ij}=1$ or $a_{ij}=0$, and $a_{ij}=a_{ji}$), but this yields the illusions
that larger groups have stronger cohesion and reach consensus more quickly,
which are both false. To sidestep these illusions, the row-normalized
adjacency matrix $\bf{W}$ is to be used instead of $\mathbf{A}$, with
$w_{ij}=a_{ij}/\sum_{j=1}^{n}a_{ij}$ such that $\sum_{j}w_{ij}=1$, in line
with social influence models in general [13]. Then, $d_{ii}=1$ for all
individuals who pay attention to at least one social contact. I have used
$\mathbf{L}=\mathbf{D}-\mathbf{W}$ for all calculations. If $w_{ij}\neq
w_{ji}$, this poses no problem in general, but completely non-reciprocal ties
($w_{ij}>0$ and $w_{ji}=0$) entail complex eigenvalues without meaningful
interpretation in social life, and hardly contribute to social cohesion.
Therefore it is best to remove them from the data, to err on the safe side.

When integrating $d\mathbf{y}/dt=-\mathbf{L}\mathbf{y}$ (Eq. 1), the solution,
$\mathbf{y}_{t}=e^{-\mathbf{L}t}\mathbf{y}_{0}$, is unpacked in terms of the
eigenvectors, $\mathbf{v}_{i}$, and eigenvalues of $\mathbf{L}$ [46]. Because
$\mathbf{y}_{0}=b_{1}\mathbf{v}_{1}+b_{2}\mathbf{v}_{2}+...+b_{n}\mathbf{v}_{n}$,

$\mathbf{y}_{t}=b_{1}e^{-\lambda_{1}t}\mathbf{v}_{1}+b_{2}e^{-\lambda_{2}t}\mathbf{v}_{2}+...+b_{n}e^{-\lambda_{n}t}\mathbf{v}_{n}.$
(3)

The outcome is dominated by the smallest eigenvalue larger than zero,
$\lambda_{2}$.

When there is variation across individuals’ susceptibilities to social
influence, thus $s_{ii}\neq s_{jj}$, Eq.1 can be expanded to

$\frac{d\bf{y}}{dt}=-\bf{S}\mathbf{L}\bf{y},$ (4)

with diagonal matrix $\bf{S}$ = $diag(s_{ii})$ and for all $i\neq j$,
$s_{ij}=0$. The larger the variation of susceptibilities, the less accurate
algebraic connectivity predicts the speed of convergence, which does not stand
in the way of solving numerically. The latter points out that stubborn
individuals (with low $s_{ii}$) have a larger influence on $\mathbf{y}_{t}$.
This is also true for leaders to whom others direct their strongest ties.

### Algebraic connectivity and social cohesion

The majority of mathematical results [47] is based on symmetric binary
matrices, instead of row-normalized matrices, including the results in this
section. The presentation follows the order of the main text.

First, the expected path length, $E(\mathcal{D})$, imposes an upper bound on
algebraic connectivity

$\lambda_{2}\geq\frac{2}{(n-1)E(\mathcal{D})-0.5(n-2)},$ (5)

and so does $\mathcal{D}_{max}$, the diameter, $\lambda_{2}\geq
4/(n\mathcal{D}_{max})$. Proofs are in [47].

Second, for all networks that are no cliques (i.e., are at least one tie
short), $\lambda_{2}\leq\mathcal{K}$, with $\mathcal{K}$ the minimum number of
nodes that have to be removed to make the network fall apart [1].
$\mathcal{K}$ also equals the minimum number of non-overlapping paths
connecting arbitrary pairs of nodes [48, 11], for which $\lambda_{2}$ thus
imposes a lower bound.

Third, to show that chords between long paths increase $\lambda_{2}$ while
keeping density constant, take the smallest chordless cycle in the network
(usually a triad), remove one tie from it, and keep it aside. Now take the
longest chordless cycle and cross-connect it midway with the tie just removed.
By means of this tie relaying, the average distance decreases, just like
random relays do in the famous small world model [49]. The procedure may be
repeated. To finish the proof, apply the expected path length theorem (Eq. 5).

Furthermore, $\lambda_{2}\leq min(k)$, the smallest degree in the network
[47].

### Data availability

The data sets are embedded in the code.

### Code availability

The R code, including all data, is available at https://osf.io/8wpxt/

## References

  * [1] Miroslav Fiedler.  Algebraic connectivity of graphs.  Czechoslovak Mathematical Journal, 23:298–305, 1973.
  * [2] Linda Argote and Dennis Epple.  Learning curves in manufacturing.  Science, 247:920–924, 1990.
  * [3] Louis E. Yelle.  The learning curve.  Decision Sciences, 10:302–328, 1979.
  * [4] Alin Coman, Ida Momennejad, Rae D. Drach, and Andra Geana.  Mnemonic convergence in social networks: The emergent properties of cognition at a collective level.  Proceedings of the National Academy of Sciences, 113:8171–8176, 2016.
  * [5] Ida Momennejad.  Collective minds: social network topology shapes collective cognition.  Philosophical Transactions of the Royal Society B, 377:20200315, 2021.
  * [6] Stephen Judd, Michael Kearns, and Yevgeniy Vorobeychik.  Behavioral dynamics and influence in networked coloring and consensus.  Proceedings of the National Academy of Sciences, 107:14978–14982, 2010.
  * [7] Damon Centola and Andrea Baronchelli.  The spontaneous emergence of conventions: An experimental study of cultural evolution.  Proceedings of the National Academy of Sciences, 112:1989–1994, 2015.
  * [8] Anton V. Proskurnikov and Roberto Tempo.  A tutorial on modeling and analysis of dynamic social networks. Part I.  Annual Reviews in Control, 43:65–79, 2017.
  * [9] Ali Jadbabaie, Nader Motee, and Mauricio Barahona.  On the stability of the Kuramoto model of coupled nonlinear oscillators.  In Proceedings of the 2004 American Control Conference, volume 5, pages 4296–4301. IEEE, 2004.
  * [10] William H. McNeill.  Keeping Together in Time: Dance and Drill in Human History.  Harvard University Press, Cambridge, MA, 1995.
  * [11] Douglas R. White and Frank Harary.  The cohesiveness of blocks in social networks.  Sociological Methodology, 31:305–359, 2001.
  * [12] Mehdi Moussaïd, Henry Brighton, and Wolfgang Gaissmaier.  The amplification of risk in experimental diffusion chains.  Proceedings of the National Academy of Sciences, 112:5631–5636, 2015.
  * [13] Noah E. Friedkin and Eugene C. Johnsen.  Social Influence Network Theory.  Cambridge University Press, Cambridge, MA, 2011.
  * [14] Atesh Koul, Davide Ahmar, Gian Domenico Iannetti, and Giacomo Novembre.  Interpersonal synchronization of spontaneously generated body movements.  Iscience, 26, 2023.
  * [15] Elizabeth Levy Paluck, Seth A. Green, and Donald P. Green.  The contact hypothesis re-evaluated.  Behavioural Public Policy, 3:129–158, 2019.
  * [16] Reza Olfati-Saber and Richard M. Murray.  Consensus problems in networks of agents with switching topology and time-delays.  IEEE Transactions on Automatic Control, 49:1520–1533, 2004.
  * [17] Károly Takács, Andreas Flache, and Michael Mäs.  Discrepancy and disliking do not induce negative opinion shifts.  PLoS ONE, 11:e0157948, 2016.
  * [18] Andreas Flache, Michael Mäs, Thomas Feliciani, Edmund Chattoe-Brown, Guillaume Deffuant, Sylvie Huet, and Jan Lorenz.  Models of social influence.  Journal of Artificial Societies and Social Simulation, 20, 2017\.
  * [19] Patrick N. McGraw and Michael Menzinger.  Analysis of nonlinear synchronization dynamics of oscillator networks by Laplacian spectral methods.  Physical Review E, 75:027104, 2007.
  * [20] Nair Maria Maia De Abreu.  Old and new results on algebraic connectivity of graphs.  Linear Algebra and its Applications, 423:53–73, 2007.
  * [21] Laura Spinney.  The shared past that wasn’t.  Nature, 543:168–170, 2017.
  * [22] Ida Momennejad, Ajua Duker, and Alin Coman.  Bridge ties bind collective memories.  Nature Communications, 10:1578, 2019.
  * [23] James Moody and Douglas R. White.  Structural cohesion and embeddedness.  American Sociological Review, 68:103–127, 2003.
  * [24] Kimmo Eriksson and Julie C. Coultas.  The advantage of multiple cultural parents in the cultural transmission of stories.  Evolution and Human Behavior, 33:251–259, 2012.
  * [25] Peter Sheridan Dodds, Roby Muhamad, and Duncan J. Watts.  An experimental study of search in global social networks.  Science, 301:827–829, 2003.
  * [26] Randall Collins.  Interaction Ritual Chains.  Princeton University Press, Princeton, NJ, 2004.
  * [27] Paul Reddish, Ronald Fischer, and Joseph Bulbulia.  Let’s dance together: Synchrony, shared intentionality and cooperation.  PLoS One, 8:e71182, 2013.
  * [28] Jeroen Bruggeman.  A Sociology of Humankind.  Routledge, New York, 2024.
  * [29] Andries E. Brouwer and Willem H. Haemers.  Spectra of Graphs.  Springer, New York, 2011.
  * [30] Allen Newell and Herbert Simon.  Human Problem Solving.  Prentice-Hall, Englewood Cliffs, NJ, 1972.
  * [31] Jeff Shrager, Tad Hogg, and Bernardo A. Huberman.  A graph-dynamic model of the power law of practice and the problem-solving fan-effect.  Science, 242:414–416, 1988.
  * [32] Bernardo A. Huberman.  The dynamics of organizational learning.  Computational and Mathematical Organization Theory, 7:145–153, 2001\.
  * [33] Damon Centola.  The spread of behavior in an online social network experiment.  Science, 329:1194–1197, 2010.
  * [34] I. L. Janis.  Victims of Groupthink.  Houghton Mifflin, Boston, 1972.
  * [35] Scott E. Page.  The Difference.  Princeton University Press, Princeton, NJ, 2007.
  * [36] Henrich R. Greve, Hayagreeva Rao, Paul Vicinanza, and Echo Yan Zhou.  Online conspiracy groups.  American Sociological Review, 87:919–949, 2022.
  * [37] Myron Glazer and Penina Migdal Glazer.  The Whistleblowers: Exposing Corruption in Government and Industry.  Basic Books, New York, 1989.
  * [38] Jeroen Bruggeman.  Solving problems in social groups.  Proceedings of the National Academy of Sciences, 114:E9183, 2017\.
  * [39] Damon Centola, Joshua Becker, Jingwen Zhang, Jaya Aysola, Douglas Guilbeault, and Elaine Khoong.  Experimental evidence for structured information-sharing networks reducing medical errors.  Proceedings of the National Academy of Sciences, 120:e2108290120, 2023.
  * [40] Michael Kearns, Siddharth Suri, and Nick Montfort.  An experimental study of the coloring problem on human subject networks.  Science, 313:824–827, 2006.
  * [41] Fabian Baumann, Philipp Lorenz-Spreen, Igor M. Sokolov, and Michele Starnini.  Modeling echo chambers and polarization dynamics in social networks.  Physical Review Letters, 124:048301, 2020.
  * [42] Fernando P. Santos, Yphtach Lelkes, and Simon A. Levin.  Link recommendation algorithms and dynamics of polarization in online social networks.  Proceedings of the National Academy of Sciences, 118:e2102141118, 2021.
  * [43] Claudio Altafini.  Consensus problems on networks with antagonistic interactions.  IEEE Transactions on Automatic Control, 58:935–946, 2013.
  * [44] Jesse Shore, Ethan Bernstein, and David Lazer.  Facts and figuring: An experimental investigation of network structure and performance in information and solution spaces.  Organization Science, 26:1432–1446, 2015.
  * [45] Fan Chung.  Spectral Graph Theory.  American Mathematical Society, Providence, RI, 2nd edition, 1997.
  * [46] Hiroki Sayama.  Introduction to the Modeling and Analysis of Complex Systems.  Open SUNY Textbooks, Geneseo, NY, 2015.
  * [47] Piet Van Mieghem.  Graph Spectra for Complex Networks.  Cambridge University Press, Cambridge, 2010.
  * [48] Karl Menger.  Zur allgemeinen Kurventheorie.  Fundamenta Mathematicae, 10:96–115, 1927.
  * [49] Duncan J. Watts and Steven H. Strogatz.  Collective dynamics of ‘small-world’ networks.  Nature, 393:440–442, 1998.


| $\rho_{t}=1$ | metric |  $96.06~{}\pm~{}\textbf{0.24}$ | $\cellcolor{NiceOrange!25}\textbf{70.59}~{}\pm~{}\textbf{22.26}$ |  $\cellcolor{NiceOrange!25}\textbf{389.06}~{}\pm~{}287.84$
|  | $\rho$ |  $1.223~{}\pm~{}0.118$ | $1.017~{}\pm~{}0.035$ |  $1.215~{}\pm~{}0.211$
| none | metric | $\cellcolor{NiceBlue!25}\textbf{96.19}~{}\pm~{}0.29$ | $62.98~{}\pm~{}27.77$ | $644.18~{}\pm~{}0.59$
|  | $\rho$ | $0.858~{}\pm~{}0.002$ | $0.871~{}\pm~{}0.001$ | $0.854~{}\pm~{}0.001$
ALIF | $\rho_{t}=1$ | metric |  $\cellcolor{NiceOrange!25}\textbf{11.27}~{}\pm~{}0.27$ |  $5.06~{}\pm~{}\textbf{0.20}$ |  $\cellcolor{NiceOrange!25}\textbf{653.87}~{}\pm~{}\textbf{2.00}$
|  | $\rho$ |  $1.938~{}\pm~{}0.910$ |  $1.026~{}\pm~{}0.006$ |  $1.169~{}\pm~{}0.177$
| none | metric | $11.08~{}\pm~{}\textbf{0.25}$ | $\cellcolor{NiceBlue!25}\textbf{5.13}~{}\pm~{}0.24$ | $655.61~{}\pm~{}12.53$
|  | $\rho$ | $2.281~{}\pm~{}0.014$ | $2.103~{}\pm~{}0.006$ | $1.650~{}\pm~{}0.023$
ALIF± | $\rho_{t}=1$ | metric |  $11.05~{}\pm~{}\textbf{0.72}$ | $16.37~{}\pm~{}16.41$ |  $\cellcolor{NiceOrange!25}\textbf{652.52}~{}\pm~{}1.29$
|  | $\rho$ |  $1.916~{}\pm~{}1.101$ | $1.018~{}\pm~{}0.014$ |  $1.395~{}\pm~{}0.610$
| none | metric | $\cellcolor{NiceBlue!25}\textbf{11.73}~{}\pm~{}1.54$ | $\cellcolor{NiceBlue!25}\textbf{17.68}~{}\pm~{}\textbf{4.21}$ | $661.75~{}\pm~{}\textbf{0.75}$
|  | $\rho$ | $1.090~{}\pm~{}0.005$ | $0.979~{}\pm~{}0.002$ | $0.973~{}\pm~{}0.001$
|  |  |  |  |
Table : task5 |  | task | sl-MNIST$\uparrow$ | SHD$\uparrow$ | PTB$\downarrow$
---|---|---|---|---|---
net | LSC |  |  |  |
RNN $\sigma$ | $\rho_{t}=0.5$ | metric | $\cellcolor{NiceGreen!25}\textbf{29.38}~{}\pm~{}6.65$ | $34.66~{}\pm~{}8.30$ | $\cellcolor{NiceGreen!25}\textbf{116.81}~{}\pm~{}7.31$
|  | $\rho$ | $0.492~{}\pm~{}0.008$ | $0.496~{}\pm~{}0.007$ | $0.497~{}\pm~{}0.003$
| $\rho_{t}=1$ | metric | $26.98~{}\pm~{}3.29$ | $36.37~{}\pm~{}\textbf{5.23}$ | $276.09~{}\pm~{}244.64$
|  | $\rho$ | $0.992~{}\pm~{}0.142$ | $1.019~{}\pm~{}0.019$ | $0.981~{}\pm~{}0.335$
| none | metric | $29.02~{}\pm~{}\textbf{2.00}$ | $\textbf{46.40}~{}\pm~{}12.12$ | $641.65~{}\pm~{}\textbf{1.76}$
|  | $\rho$ | $0.354~{}\pm~{}0.002$ | $0.363~{}\pm~{}0.001$ | $0.353~{}\pm~{}0.000$
RNN $ReLU$ | $\rho_{t}=0.5$ | metric | $\cellcolor{NiceGreen!25}\textbf{28.12}~{}\pm~{}3.41$ | $35.46~{}\pm~{}10.64$ | $\cellcolor{NiceGreen!25}\textbf{158.79}~{}\pm~{}10.43$
|  | $\rho$ | $0.500~{}\pm~{}0.003$ | $0.508~{}\pm~{}0.003$ | $0.516~{}\pm~{}0.002$
| $\rho_{t}=1$ | metric | $24.80~{}\pm~{}5.44$ | $33.34~{}\pm~{}\textbf{4.90}$ | $167.83~{}\pm~{}13.57$
|  | $\rho$ | $0.997~{}\pm~{}0.009$ | $0.945~{}\pm~{}0.177$ | $1.019~{}\pm~{}0.004$
| none | metric | $23.51~{}\pm~{}\textbf{2.50}$ | $\textbf{39.84}~{}\pm~{}5.91$ | $173.67~{}\pm~{}\textbf{3.21}$
|  | $\rho$ | $1.317~{}\pm~{}0.011$ | $1.349~{}\pm~{}0.007$ | $0.760~{}\pm~{}0.004$
GRU | $\rho_{t}=0.5$ | metric | $\cellcolor{NiceGreen!25}\textbf{95.28}~{}\pm~{}\textbf{0.17}$ | $\cellcolor{NiceGreen!25}\textbf{85.58}~{}\pm~{}\textbf{1.35}$ | $\cellcolor{NiceGreen!25}\textbf{103.12}~{}\pm~{}0.25$
|  | $\rho$ | $0.482~{}\pm~{}0.020$ | $0.491~{}\pm~{}0.006$ | $0.499~{}\pm~{}0.001$
| $\rho_{t}=1$ | metric | $95.04~{}\pm~{}0.75$ | $84.40~{}\pm~{}2.21$ | $103.41~{}\pm~{}0.78$
|  | $\rho$ | $0.999~{}\pm~{}0.004$ | $1.003~{}\pm~{}0.005$ | $1.002~{}\pm~{}0.004$
| none | metric | $94.85~{}\pm~{}0.40$ | $84.92~{}\pm~{}2.05$ | $103.78~{}\pm~{}\textbf{0.21}$
|  | $\rho$ | $0.710~{}\pm~{}0.004$ | $0.719~{}\pm~{}0.002$ | $0.694~{}\pm~{}0.002$
LSTM | $\rho_{t}=0.5$ | metric | $95.21~{}\pm~{}\textbf{0.24}$ |  NiceGreen!25$\textbf{84.48}\pm\textbf{0.97}$ | $\cellcolor{NiceGreen!25}\textbf{108.83}\pm\textbf{1.65}$
|  | $\rho$ | $0.503~{}\pm~{}0.006$ | $0.516~{}\pm~{}0.026$ | $0.511~{}\pm~{}0.016$
| $\rho_{t}=1$ | metric | $\cellcolor{NiceOrange!25}\textbf{95.60}~{}\pm~{}0.40$ | $82.87~{}\pm~{}2.75$ | $109.93~{}\pm~{}1.90$
|  | $\rho$ | $0.985~{}\pm~{}0.038$ | $0.997~{}\pm~{}0.014$ | $1.000~{}\pm~{}0.018$
| none | metric | $95.21~{}\pm~{}0.95$ | $83.61~{}\pm~{}1.97$ | $108.93~{}\pm~{}2.83$
|  | $\rho$ | $0.876~{}\pm~{}0.005$ | $0.887~{}\pm~{}0.002$ | $0.847~{}\pm~{}0.003$
ALIF+ | $\rho_{t}=1$ | metric | $\cellcolor{NiceOrange!25}\textbf{86.45}~{}\pm~{}\textbf{3.30}$ | $\cellcolor{NiceOrange!25}\textbf{83.18}~{}\pm~{}\textbf{0.95}$ | $\cellcolor{NiceOrange!25}\textbf{129.82}\pm\textbf{0.96}$
|  | $\rho$ | $0.988~{}\pm~{}0.003$ | $1.001~{}\pm~{}0.001$ | $0.978\pm 0.208$
| none | metric | $86.38~{}\pm~{}5.16$ | $70.26~{}\pm~{}7.12$ | $130.18~{}\pm~{}1.06$
|  | $\rho$ | $2.225~{}\pm~{}0.033$ | $1.748~{}\pm~{}0.016$ | $1.690~{}\pm~{}0.022$
ALIF± | $\rho_{t}=1$ | metric | $\cellcolor{NiceOrange!25}\textbf{82.05}~{}\pm~{}6.26$ | $\cellcolor{NiceOrange!25}\textbf{73.98}~{}\pm~{}\textbf{3.75}$ |  NiceOrange!25$\textbf{125.80}\pm\textbf{0.59}$
|  | $\rho$ | $0.999~{}\pm~{}0.001$ | $1.000~{}\pm~{}0.000$ | $0.981~{}\pm~{}0.002$
| none | metric | $81.42~{}\pm~{}\textbf{1.17}$ | $68.20~{}\pm~{}6.85$ | $130.54~{}\pm~{}5.09$
|  | $\rho$ | $1.212~{}\pm~{}0.007$ | $1.130~{}\pm~{}0.003$ | $1.094~{}\pm~{}0.002$
|  |  |  |  |
Table : Pre-training $d$-RNN to stability improves training across tasks and neuron models. The network preparation by pre-training to stability, generally helps performance, with $\rho_{t}=0.5$ (green) generally being preferable over $\rho_{t}=1$ (orange) across tasks and networks, with networks of depth $d=2$. Here we report the test set results across three different tasks. Metrics are accuracy for sl-MNIST and SHD, the higher the better ($\uparrow$), and perplexity for PTB, the lower the better ($\downarrow$). The non-differentiable networks, were often unable to reach a target norm of $\rho_{t}=0.5$, but the preparation to $\rho_{t}=1$ was still always beneficial. Method | sCIFAR | ListOps | Text | Retrieval | Pathfinder | PathX | Average
---|---|---|---|---|---|---|---
S4D [orvieto2023resurrecting] |  91.5 (0.2) | 60.2 (0.3) | 86.4 (0.0) | 89.5 (0.0) | 94.2 (0.3) | 97.5 (0.0) | 86.6
S5 [orvieto2023resurrecting] | 88.8 (0.1) | 58.5 (0.3) | 86.2 (0.1) | 88.9 (0.0) |  95.7 (0.1) | 96.0 (0.1) | 85.7
S4 [gu2022efficiently] | 91.1 | 59.6 | 86.8 | 90.9 | 94.2 | 96.4 | 86.5
S4D-LegS [gu2022parameterization] | 89.9 | 60.5 | 86.2 | 89.5 | 93.1 | 91.9 | 85.2
S5 [smith2023simplified] | 88.0 | 62.2 | 89.3 | 91.4 | 95.3 | 98.6 | 87.8
LRU [orvieto2023resurrecting] | 89.0 (0.1) | 60.2 (0.8) |  89.4 (0.1) | 89.9 (0.1) | 95.1 (0.1) | 94.2 (0.4) | 86.2
(ours) |  |  |  |  |  |  |
S5 | - | - | - | - | - | - | -
LRU | - | - | - | - | - | - | -
LRU + LSC $\rho_{t}=1$ | - | - | - | - | - | - | -
LRU + LSC $\rho_{t}=0.5$ | - | - | - | - | - | - | -
LRU + LSC $\overline{\rho}_{t}=0.5$ | - | - | - | - | - | - | -
LRU + clip | - | - | - | - | - | - | -
LRU + LSC $\rho_{t}=1$ \+ clip | - | - | - | - | - | - | -
LRU + LSC $\rho_{t}=0.5$ \+ clip | - | - | - | - | - | - | -
LRU + LSC $\overline{\rho}_{t}=0.5$ \+ clip | - | - | - | - | - | - | -