# Multi-agent Natural Actor-critic Reinforcement Learning Algorithms

Prashant Trivedi
Industrial Engineering and Operations Research
Indian Institute of Technology Bombay India
<EMAIL_ADDRESS>
&Nandyala Hemachandra
Industrial Engineering and Operations Research
Indian Institute of Technology Bombay India
<EMAIL_ADDRESS>
###### Abstract

Multi-agent actor-critic algorithms are an important part of the Reinforcement
Learning paradigm. We propose three fully decentralized multi-agent natural
actor-critic (MAN) algorithms in this work. The objective is to collectively
find a joint policy that maximizes the average long-term return of these
agents. In the absence of a central controller and to preserve privacy, agents
communicate some information to their neighbors via a time-varying
communication network. We prove convergence of all the 3 MAN algorithms to a
globally asymptotically stable set of the ODE corresponding to actor update;
these use linear function approximations. We show that the Kullback-Leibler
divergence between policies of successive iterates is proportional to the
objective function’s gradient. We observe that the minimum singular value of
the Fisher information matrix is well within the reciprocal of the policy
parameter dimension. Using this, we theoretically show that the optimal value
of the deterministic variant of the MAN algorithm at each iterate dominates
that of the standard gradient-based multi-agent actor-critic (MAAC) algorithm.
To our knowledge, it is a first such result in multi-agent reinforcement
learning (MARL). To illustrate the usefulness of our proposed algorithms, we
implement them on a bi-lane traffic network to reduce the average network
congestion. We observe an almost 25% reduction in the average congestion in 2
MAN algorithms; the average congestion in another MAN algorithm is on par with
the MAAC algorithm. We also consider a generic $15$ agent MARL; the
performance of the MAN algorithms is again as good as the MAAC algorithm.

_Keywords_ Natural Gradients $\cdot$ Actor-Critic Methods $\cdot$ Networked
Agents $\cdot$ Traffic Network Control $\cdot$ Stochastic Approximations
$\cdot$ Function Approximations $\cdot$ Fisher Information Matrix $\cdot$ Non-
Convex Optimization $\cdot$ Quasi second-order methods $\cdot$ Local optima
value comparison $\cdot$ Algorithms for better local minima

##  1 Introduction

Reinforcement learning (RL) has been explored in recent years and is of great
interest to researchers because of its broad applicability in many real-life
scenarios. In RL, agents interact with the environment and take decisions
sequentially. It is applied successfully to various problems, including
elevator scheduling, robot control, etc. There are many instances where RL
agents surpass human performance, such as openAI beating the world champion
DOTA player, DeepMind beating the world champion of Alpha Star.

The sequential decision-making problems are generally modeled via Markov
decision process (MDP). It requires the knowledge of system transitions and
rewards. In contrast, RL is a data-driven MDP framework for sequential
decision-making tasks; the transition probability matrices and the reward
functions are not assumed, but their realizations are available as observed
data.

In RL, the purpose of an agent is to learn an optimal or nearly-optimal policy
that maximizes the “reward function” or functions of other user-provided
“reinforcement signals” from the observed data. However, in many realistic
scenarios, there is more than one agent. To this end, researchers explore the
multi-agent reinforcement learning (MARL) methods, but most are centralized
and relatively slow. Furthermore, these MARL algorithms use the
standard/vanilla gradient, which has limitations. For example, the standard
gradients cannot capture the angles in the state space and may not be
effective in many scenarios. The natural gradients are more suitable choices
because they capture the intrinsic curvature in the state space. In this work,
we are incorporating natural gradients in the MARL framework.

In the multi-agent setup that we consider, the agents have some private
information and a common goal. This goal could be achieved by deploying a
central controller and converting the MARL problem into a single-agent RL
problem. However, deploying a central controller often leads to scalability
issues. On the other hand, if there is no central controller and the agents do
not share any information then there is almost no hope of achieving the common
goal. An intermediate model is to share some parameters via (possibly) a time-
varying, and sparse communication matrix [Zhang et al., 2018]. The algorithms
based on such intermediate methods are often attributed as consensus based
algorithms.

The consensus based algorithm models can also be considered as intermediate
between dynamic non-cooperative and cooperative game models. Non-cooperative
games, as multi-agent systems, model situations where the agents do not have a
common goal and do not communicate. On the contrary, cooperative games model
situations where a central controller achieves a common goal using complete
information.

Algorithm 2 of [Zhang et al., 2018] is a consensus based actor-critic
algorithm. We call it MAAC (multi-agent actor-critic) algorithm. The MAAC
algorithm uses the standard gradient and hence lacks in capturing the
intrinsic curvature present in the state space. We propose three multi-agent
natural actor-critic (MAN) algorithms and incorporate the curvatures via
natural gradients. These algorithms use the linear function approximations for
the state value and reward functions. We prove the convergence of all the 3
MAN algorithms to a globally asymptotically stable equilibrium set of ordinary
differential equations (ODEs) obtained from the actor updates.

Here is a brief overview of our two time-scale approach. Let $J(\theta)$ be
the global MARL objective function of $n$ agents, where
$\theta=(\theta^{1},\dots,\theta^{n})$ is the actor (or policy) parameter. For
a given policy parameter $\theta$ of each MAN algorithm, we first show in
Theorem 4 the convergence of critic parameters (to be defined later) on a
faster time scale. Note that these critic parameters are updated via the
communication matrix. We then show the convergence of each agent’s actor
parameters to an asymptotically stable attractor set of its ODE. These actor
updates use the natural gradients in the form of Fisher information matrix and
advantage parameters (Theorem 6, 8 and 10). The actor parameter $\theta$ is
shown to converge on the slower time scale.

Our MAN algorithms use a log-likelihood function via the Fisher information
matrix and incorporate the curvatures. We show that this log-likelihood
function is indeed the KL divergence between the consecutive policies, and it
is the gradient of the objective function up to scaling (Lemma 1). Unlike
standard gradient methods, where the updates are restricted to the parameter
space only, the natural gradient-based methods allow the updates to factor in
the curvature of the policy distribution prediction space via the KL
divergence between them. Thus, 2 of our MAN algorithms, FI-MAN and FIAP-MAN,
use a certain _representation_ of the objective function gradient in terms of
the gradient of this KL divergence (Lemma 1). It turns out these two
algorithms have much better empirical performance (Section 5.1).

We now point out a couple of important consequences of the representation
learning aspect of our MAN algorithms for reinforcement learning. First, we
show that under some conditions, our deterministic version of the FI-MAN
algorithm converges to local minima with a better objective function value
than the deterministic counterpart of the MAAC algorithm, Theorem 3. To the
best of our knowledge, this is a new result in non-convex optimization; we are
not aware of any algorithm that is _proven_ to converge to a better local
maxima [Bottou et al., 2018, Nocedal and Wright, 2006]. This relies on the
important observation, which can be of independent interest, that $1/m$ is
_uniform_ upper bound on the smallest singular value of Fisher information
matrix $G(\theta)$, Lemma 2; here $m$ is the common dimension of the
compatible policy parameter $\theta$ and the Fisher information matrix
$G(\theta)$.

The natural gradient-based methods can be viewed as quasi-second order
methods, as the Fisher information matrix $G(\cdot)$ is an invertible linear
transformation of basis that is used in first-order optimization methods
[Agarwal et al., 2021]. However, they are not regarded as second-order methods
because the Fisher information matrix is not the Hessian of the objective
function.

To validate the usefulness of our proposed algorithms, we perform a
comprehensive set of computational experiments in two settings: a bi-lane
traffic network and an abstract MARL model. On a bi-lane traffic network
model, the objective is to find the traffic signaling plan that reduces the
overall network congestion. We consider two different arrival patterns between
various origin-destination (OD) pairs. With the suitable linear function
approximations to incorporate the humongous state space $(50^{16})$ and action
space $(3^{4})$, we observe a significant reduction ($\approx 25\%$) in the
average network congestion in 2 of our MAN algorithms. One of our MAN
algorithms that are only based on the advantage parameters and never estimate
the Fisher information matrix inverse is on-par with the MAAC algorithm. In
the abstract MARL model, we consider $15$ agents with 15 states and 2 actions
in each state and generic reward functions [Dann et al., 2014, Zhang et al.,
2018]. Each agent’s reward is private information and hence not known to other
agents. Our MAN algorithms either outperform or are on-par with the MAAC
algorithm with high confidence.

Organization of the paper: In Section 2 we introduce the multi-agent
reinforcement learning (MARL) and a novel natural gradients framework. We then
propose MAN algorithms, namely FI-MAN, AP-MAN, and FIAP-MAN, and provide some
theoretical insights on their relative performance in Section 3. Convergence
proofs of all the algorithms are available in Section 4. Finally, we provide
the computational experiments for modeling traffic network control and another
abstract MARL problem in Section 5.

The detailed proof of theorems and lemmas are available in Appendix A. More
details of the computations and empirical observations are available in
Appendix B. We provide some backgrounds on MDP, single-agent actor-critic
algorithm, and the MAAC algorithms in Appendix C.

##  2 MARL framework and natural gradients

This section describes the multi-agent reinforcement learning (MARL) framework
and the notion of natural gradients. We first describe some basic notations
and the multi-agent Markov decision process (MDP).

Let $N=\\{1,2,\dots,n\\}$ denote the set of agents. Each agent independently
interacts with a stochastic environment and takes a local action. We consider
a fully decentralized setup in which a communication network connect the
agents. This network is used to exchange information among agents in the
absence of a central controller so that agents’ privacy remains intact. The
communication network is possibly time-varying and sparse. We assume the
communication among agents is synchronized, and hence there are no information
delays. Moreover, only some parameters (that we define later) are shared among
the neighbors of each agent. It also addresses an important aspect of the
privacy protection of such agents. Formally, the communication network is
characterized by an undirected graph $\mathcal{G}_{t}=(N,\mathcal{E}_{t})$,
where $N$ is the set of all nodes (or agents) and $\mathcal{E}_{t}$ is the set
of communication links available at time $t\in\mathbb{N}$. We say, agents
$i,j\in N$ communicate at time $t$ if $(i,j)\in\mathcal{E}_{t}$.

Let $\mathcal{S}$ denote the common state space available to all the agents.
At any time $t$, each agent observes a common state $s_{t}\in\mathcal{S}$, and
takes a local action $a^{i}_{t}$ from the set of available actions
$\mathcal{A}^{i}$. We assume that for any agent $i\in N$, the entire action
set $\mathcal{A}^{i}$ is feasible in every state, $s\in\mathcal{S}$. The
action $a^{i}_{t}$ is taken as per a local policy
$\pi^{i}:\mathcal{S}\times\mathcal{A}^{i}\rightarrow[0,1]$, where
$\pi^{i}(s_{t},a^{i}_{t})$ is the probability of taking action $a^{i}_{t}$ in
state $s_{t}$ by agent $i\in N$. Let
$\mathcal{A}:=\prod_{i=1}^{n}\mathcal{A}^{i}$ be the joint action space of all
the agents. To each state and action pair, every agent receives a finite
reward from the local reward function
${R}^{i}:\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R}$. Note that the
reward is private information of the agent and it is not known to other
agents. The state transition probability of MDP is given by
$P:\mathcal{S}\times\mathcal{A}\times\mathcal{S}\rightarrow[0,1]$. Using only
local rewards and actions it is hard for any classical reinforcement learning
algorithm to maximize the averaged reward determined by the joint actions of
all the agents. To this end, we consider the multi-agent networked MDP given
in [Zhang et al., 2018]. The multi-agent networked MDP is defined as
$(\mathcal{S},\\{\mathcal{A}^{i}\\}_{i\in N},P,\\{R^{i}\\}_{i\in
N},\\{\mathcal{G}_{t}\\}_{t\geq 0})$, with each component described as above.
Let joint policy of all agents be denoted by
$\pi:\mathcal{S}\times\mathcal{A}\rightarrow[0,1]$ satisfying
$\pi(s,a)=\prod_{i\in N}\pi^{i}(s,a^{i})$. Let
$a_{t}=(a^{1}_{t},\dots,a^{n}_{t})$ be the action taken by all the agents at
time $t$. Depending on the action $a^{i}_{t}$ taken by agent $i$ at time $t$,
the agent receives a random reward $r^{i}_{t+1}$ with the expected value
$R^{i}(s_{t},a_{t})$. Moreover, with probability $P(s_{t+1}|s_{t},a_{t})$ the
multi-agent MDP shifts to next state $s_{t+1}\in\mathcal{S}$.

Due to the large state and action space, it is often helpful to consider the
parameterized policies [Grondman et al., 2012, Sutton and Barto, 2018]. We
parameterize the local policy, $\pi^{i}(\cdot,\cdot)$ by
$\theta^{i}\in\Theta^{i}\subseteq\mathbb{R}^{m_{i}}$, where $\Theta^{i}$ is
the compact set. To find the global policy parameters we can pack all the
local policy parameters as
$\theta=[(\theta^{1})^{\top},\dots,(\theta^{n})^{\top}]^{\top}\in\Theta\subseteq\mathbb{R}^{m}$,
where $\Theta:=\prod_{i\in N}\Theta^{i}$, and $m=\sum_{i=1}^{n}m_{i}$. The
parameterized joint policy is then given by $\pi_{\theta}(s,a)=\prod_{i\in
N}\pi^{i}_{\theta^{i}}(s,a^{i})$. The objective of the agents is to
collectively find a joint policy $\pi_{\theta}$ that maximizes the averaged
long-term return, provided each agent has local information only. For a given
policy parameter $\theta$, let the globally averaged long-term return be
denoted by $J(\theta)$ and defined as

$J(\theta)=lim_{T\rightarrow\infty}~{}\frac{1}{T}\mathbb{E}\left(\sum_{t=0}^{T-1}\frac{1}{n}\sum_{i\in{N}}r^{i}_{t+1}\right)=\sum_{s\in\mathcal{S}}d_{\theta}(s)\sum_{a\in\mathcal{A}}\pi_{\theta}(s,a)\bar{R}(s,a),$

where $\bar{R}(s,a)=\frac{1}{n}\sum_{i\in{N}}R^{i}(s,a)$ is the globally
averaged reward function. Let
$\bar{r}_{t}=\frac{1}{n}\sum_{i\in{N}}r^{i}_{t}$. Thus
$\bar{R}(s,a)=\mathbb{E}[\bar{r}_{t+1}|s_{t}=s,a_{t}=a]$. Therefore, the joint
objective of the agents is to solve the following optimization problem

$max_{\theta}~{}J(\theta)=max_{\theta}~{}\sum_{s\in\mathcal{S}}d_{\theta}(s)\sum_{a\in\mathcal{A}}\pi_{\theta}(s,a)\bar{R}(s,a).$
(1)

Like single-agent RL [Bhatnagar et al., 2009a], we also require the following
regularity assumption on networked multi-agent MDP and parameterized policies.

######  X. 1.

For each agent $i\in N$, the local policy function
$\pi^{i}_{\theta^{i}}(s,a^{i})>0$ for any
$s\in\mathcal{S},a^{i}\in\mathcal{A}^{i}$ and $\theta^{i}\in\Theta^{i}$. Also
$\pi^{i}_{\theta^{i}}(s,a^{i})$ is continuously differentiable with respect to
parameters $\theta^{i}$ over $\Theta^{i}$. Moreover, for any
$\theta\in\Theta$, $P^{\theta}$ is the transition matrix for the Markov chain
$\\{s_{t}\\}_{t\geq 0}$ induced by policy $\pi_{\theta}$, that is, for any
$s,s^{\prime}\in\mathcal{S}$,

$P^{\theta}(s^{\prime}|s)=\sum_{a\in\mathcal{A}}\pi_{\theta}(s,a)P(s^{\prime}|s,a).$

Furthermore, the Markov chain $\\{s_{t}\\}_{t\geq 0}$ is assumed to be ergodic
under $\pi_{\theta}$ with stationary distribution $d_{\theta}(s)$ over
$\mathcal{S}$.

The regularity assumption X. 1 on a multi-agent networked MDP is standard in
the work of single agent actor-critic algorithms with function approximations
[Konda and Tsitsiklis, 2000, Bhatnagar et al., 2009a]. The continuous
differentiability of policy $\pi_{\theta}(\cdot,\cdot)$ with respect to
$\theta$ is required in policy gradient theorem [Sutton and Barto, 2018], and
it is commonly satisfied by well-known class of functions such as neural
networks or deep neural networks. Moreover, assumption X. 1 also implies that
the Markov chain $\\{(s_{t},a_{t})\\}_{t\geq 0}$ has stationary distribution
$\tilde{d}_{\theta}(s,a)=d_{\theta}(s)\cdot\pi_{\theta}(s,a)$ for any
$s\in\mathcal{S},a\in\mathcal{A}$.

Based on the objective function given in Equation (1) the global state-action
value function associated with state-action pair $(s,a)$ for a given policy
$\pi_{\theta}$ is defined as

$Q_{\theta}(s,a)=\sum_{t\geq
0}\mathbb{E}[\bar{r}_{t+1}-J(\theta)|s_{0}=s,a_{0}=a,\pi_{\theta}].$ (2)

Note that the global state-action value function, $Q_{\theta}(s,a)$ given in
Equation (2) is motivated from the gain and bias relation for the average
reward criteria of the single agent MDP as given in say, Section 8.2.1 in
[Puterman, 2014]. It captures the expected sum of fluctuations of the global
rewards about the globally averaged objective function (‘average adjusted sum
of rewards’ [Mahadevan, 1996]) when action $a=(a^{1},a^{2},\dots,a^{n})$ is
taken in state $s\in\mathcal{S}$ at time $t=0$, and thereafter the policy
$\pi_{\theta}$ is followed. Similarly, the global state value function is
defined as

$V_{\theta}(s)=\sum_{a\in\mathcal{A}}\pi_{\theta}(s,a)\cdot Q_{\theta}(s,a).$
(3)

We now state the policy gradient theorem for MARL setup [Zhang et al., 2018].
To this end, define the global advantage function
$A_{\theta}(s,a):=Q_{\theta}(s,a)-V_{\theta}(s)$. Note that the advantage
function captures the benefit of taking action $a$ in state $s$ and thereafter
following the policy $\pi_{\theta}$ over the case when policy $\pi_{\theta}$
is followed from state $s$ itself. For the multi-agent setup, we define the
local advantage function
$A^{i}_{\theta}:\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R}$ for each
agent $i\in N$ as
$A^{i}_{\theta}(s,a):=Q_{\theta}(s,a)-\widetilde{V}^{i}_{\theta}(s,a^{-i})$,
where $\widetilde{V}^{i}_{\theta}(s,a^{-i}):=\sum_{a^{i}\in
A^{i}}\pi^{i}_{\theta^{i}}(s,a^{i})Q_{\theta}(s,a^{i},a^{-i})$. Note that
$\widetilde{V}^{i}_{\theta}(s,a^{-i})$ represents the value of state $s$ to an
agent $i\in N$ when policy, $\pi(\cdot,\cdot)$ is parameterized by
$\theta=[(\theta^{1})^{\top},(\theta^{2})^{\top},\dots,(\theta^{n})^{\top}]$,
and all other agents are taking action
$a^{-i}=(a^{1},\dots,a^{i-1},a^{i+1},\dots,a^{n})$.

######  Theorem 1 (Policy gradient theorem for MARL [Zhang et al., 2018]).

Under assumption X. 1, for any $\theta\in\Theta$, and each agent $i\in N$, the
gradient of $J(\theta)$ with respect to $\theta^{i}$ is given by

$\displaystyle\nabla_{\theta^{i}}J(\theta)$ $\displaystyle=$
$\displaystyle\mathbb{E}_{s\sim
d_{\theta},a\sim\pi_{\theta}}[\nabla_{\theta^{i}}\log\pi^{i}_{\theta^{i}}(s,a^{i})\cdot
A_{\theta}(s,a)]$ $\displaystyle=$ $\displaystyle\mathbb{E}_{s\sim
d_{\theta},a\sim\pi_{\theta}}[\nabla_{\theta^{i}}\log\pi^{i}_{\theta^{i}}(s,a^{i})\cdot
A^{i}_{\theta}(s,a)].$

The proof of this theorem is available in [Zhang et al., 2018]. For the sake
of completeness we provide the proof in Appendix A.1. The idea of the proof is
as follows: We first recall the policy gradient theorem for single agent. Now
using the fact that for multi-agent case the global policy is product of local
policies, i.e.,
$\pi_{\theta}(s,a)=\prod_{i=1}^{n}\pi^{i}_{\theta^{i}}(s,a^{i})$, and
$\sum_{a^{i}\in\mathcal{A}^{i}}\pi^{i}_{\theta^{i}}(s,a^{i})=1$, hence
$\nabla_{\theta^{i}}\left[\sum_{a^{i}\in\mathcal{A}^{i}}\pi^{i}_{\theta^{i}}(s,a^{i})\right]=0$,
we show $\nabla_{\theta^{i}}J(\theta)=\mathbb{E}_{s\sim
d_{\theta},a\sim\pi_{\theta}}[\nabla_{\theta^{i}}\log\pi^{i}_{\theta^{i}}(s,a^{i})\cdot
Q_{\theta}(s,a)]$. Now, observe that adding/subtracting any function $\Lambda$
that is independent of the action $a^{i}$ taken by agent $i\in N$ to
$Q_{\theta}(s,a)$ doesn’t make any difference in the above expected value. In
particular, considering two such $\Lambda$ functions $V_{\theta}(s)$ and
$\tilde{V}_{\theta}^{i}(s,a^{-i})$, we have desired results.

We refer to
$\psi^{i}(s,a^{i}):=\nabla_{\theta^{i}}\log\pi^{i}_{\theta^{i}}(s,a^{i})$ as
the score function. We will see in Section 3.2 that the same score function is
called the compatible features. This is because the above policy gradient
theorem with function approximations require the compatibility condition
(Theorem 2 [Sutton et al., 1999]). The policy gradient theorem for MARL
relates the gradient of the global objective function w.r.t. $\theta^{i}$ and
the local advantage function $A^{i}_{\theta}(\cdot,\cdot)$. It also suggests
that the global objective function’s gradients can be obtained solely using
the local score function, $\psi^{i}(s,a^{i})$ if agent $i\in N$ has an
unbiased estimate of the advantage functions $A^{i}_{\theta}$ or $A_{\theta}$.
However, estimating the advantage function requires the rewards $r^{i}_{t}$ of
all the agents $i\in N$; therefore, these functions cannot be well estimated
by any agent $i\in N$ alone. To this end, [Zhang et al., 2018] have proposed
two fully decentralized actor-critic algorithms based on the consensus
network. These algorithms work in a fully decentralized fashion and
empirically achieve the same performance as a centralized algorithm in the
long run. We use algorithm 2 of [Zhang et al., 2018] which we are calling as
multi-agent actor-critic (MAAC) algorithm.

In the fully decentralized setup, we consider the weight matrix
$C_{t}=[c_{t}(i,j)]$, depending on the network topology of communication
network $\mathcal{G}_{t}$. Here $c_{t}(i,j)$ represents the weight of the
message transmitted from agent $i$ to agent $j$ at time $t$. At any time $t$,
the local parameters are updated by each agent using this weight matrix. For
generality, we take the weight matrix $C_{t}$ to be random. This is either
because $\mathcal{G}_{t}$ is a time-varying graph or the randomness in the
consensus algorithm [Boyd et al., 2006]. The weight matrix satisfies the
following assumptions [Zhang et al., 2018].

######  X. 2.

The sequence of non-negative random matrices $\\{C_{t}\\}_{t\geq
0}\subseteq\mathbb{R}^{n\times n}$ satisfy the following:

  1. 1.

$C_{t}$ is row stochastic, i.e., $C_{t}\mathbbm{1}=\mathbbm{1}$. Moreover,
$\mathbb{E}(C_{t})$ is column stochastic, i.e.,
$\mathbbm{1}^{\top}\mathbb{E}(C_{t})=\mathbbm{1}^{\top}$. Furthermore, there
exists a constant $\gamma\in(0,1)$ such that for any $c_{t}(i,j)>0$, we have
$c_{t}(i,j)\geq\gamma$.

  2. 2.

Weight matrix $C_{t}$ respects $\mathcal{G}_{t}$, i.e., $c_{t}(i,j)=0$ if
$(i,j)\notin\mathcal{E}_{t}$.

  3. 3.

The spectral norm of
$\mathbb{E}[C_{t}^{\top}(I-\mathbbm{1}\mathbbm{1}^{\top}/n)C_{t}]$ is smaller
than one.

  4. 4.

Given the $\sigma$-algebra generated by the random variables before time $t$,
$C_{t}$ is conditionally independent of $r^{i}_{t+1}$ for each $i\in{N}$.

Assumption X. 2(1) of considering a doubly stochastic matrix is standard in
the work of consensus-based algorithms [Mathkar and Borkar, 2016]. It is often
helpful in the convergence of the update to a common vector [Bianchi et al.,
2013]. To prove the stability of the consensus update (see Appendix A of
[Zhang et al., 2018] for detailed proof), we require the lower bound on the
weights of the matrix [Nedic and Ozdaglar, 2009]. Assumption X. 2(2) is
required for the connectivity of $\mathcal{G}_{t}$. To provide the geometric
convergence in distributed optimization, authors in [Nedic et al., 2017]
provide the connection between the time-varying network and the spectral norm
property. The same connection is required for convergence in our work also. To
this end, we have assumption X. 2(3) above. Assumption X. 2(4) on the
conditional independence of $C_{t}$ and $r_{t+1}$ is common in many practical
multi-agent systems. The Metropolis matrix [Xiao et al., 2005] given below
satisfy all the assumptions. It is defined only based on the local information
of the agents. Let $N_{t}(i):=\\{j\in N:(i,j)\in\mathcal{E}_{t}\\}$ be set of
neighbors of agent $i\in N$ at time $t$ in the weight matrix $C_{t}$, and
$d_{t}(i)=|N_{t}(i)|$ is the degree of agent $i\in N$. The weights
$c_{t}(i,j)$ in the Metropolis matrix are given by

$\displaystyle c_{t}(i,j)$ $\displaystyle=$
$\displaystyle\frac{1}{1+max\\{d_{t}(i),d_{t}(j)\\}},~{}~{}\forall~{}(i,j)\in\mathcal{E}_{t}$
$\displaystyle c_{t}(i,i)$ $\displaystyle=$ $\displaystyle 1-\sum_{j\in
N_{t}(i)}c_{t}(i,j),~{}~{}\forall~{}i\in N.$

Now, we will outline the actor-critic algorithm using linear function
approximations in a fully decentralized setting. The actor-critic algorithm
consists of two steps – critic step and actor step. At each time $t$, the
actor suggests a policy parameter $\theta_{t}$. The critic evaluates its value
using the policy parameters and criticizes or gives the feedback to the actor.
Using this feedback from critic, the actor then update the policy parameters,
and this continues until convergence. Let the global state value temporal
difference (TD) error be defined as
$\bar{\delta}_{t}=\bar{r}_{t+1}-J(\theta)+V_{\theta}(s_{t+1})-V_{\theta}(s_{t})$.
It is known that the state value temporal difference error is an unbiased
estimate of the advantage function $A_{\theta}$ [Sutton and Barto, 2018],
i.e.,

$\mathbb{E}[\bar{\delta}_{t}~{}|~{}s_{t}=s,a_{t}=a,\pi_{\theta}]=A_{\theta}(s,a),~{}~{}\forall~{}s\in\mathcal{S},~{}a\in\mathcal{A}.$
(4)

The TD error specifies how different the new value is from the old prediction.
Often in many applications [Corke et al., 2005, Dall’Anese et al., 2013] the
state space is either large or infinite. To this end, we use the linear
function approximations for state value function. Later on, we also use the
linear function approximation for the advantage function in Section 3.2. Let
the state value function $V_{\theta}(s)$ be approximated using the linear
function as $V_{\theta}(s;v):=v^{\top}\varphi(s)$, where
$\varphi(s)=[\varphi_{1}(s),\dots,\varphi_{L}(s)]^{\top}\in\mathbb{R}^{L}$ is
the feature associated with state $s$, and $v\in\mathbb{R}^{L}$. Note that
$L<<|\mathcal{S}|$, hence the value function is approximated using very small
number of features. Moreover, let $\mu^{i}_{t}$ be the estimate of the global
objective function $J(\theta)$ by agent $i\in N$ at time $t$. Note that
$\mu^{i}_{t}$ tracks the long-term return to each agent $i\in N$. The MAAC
algorithm is based on the consensus network (details in Appendix C.4) and
consists of the following updates for objective function estimate and the
critic parameters

$\displaystyle\tilde{\mu}^{i}_{t}=(1-\beta_{v,t})\cdot\mu^{i}_{t}+\beta_{v,t}\cdot
r^{i}_{t+1};~{}~{}\mu^{i}_{t+1}=\sum_{j\in{N}}c_{t}(i,j)\tilde{\mu}^{j}_{t}$
(5)
$\displaystyle\tilde{v}^{i}_{t}=v^{i}_{t}+\beta_{v,t}\cdot\delta^{i}_{t}\cdot\nabla_{v}V_{t}(v^{i}_{t});~{}~{}v^{i}_{t+1}=\sum_{j\in{N}}c_{t}(i,j)\tilde{v}^{j}_{t},$
(6)

where $\beta_{v,t}>0$ is the critic step-size and
$\delta^{i}_{t}=r^{i}_{t+1}-\mu^{i}_{t}+V_{t+1}(v^{i}_{t})-V_{t}(v^{i}_{t})$
is the local TD error. Here
$V_{t+1}(v^{i}_{t}):=v_{t}^{i^{\top}}\varphi(s_{t+1})$, and hence
$V_{t+1}(v^{i}_{t})=V_{\theta}(s_{t+1};v^{i}_{t})$. It is a linear function
approximation of the state value function, $V_{\theta}(s_{t+1})$ by agent
$i\in N$. Note that the estimate of the advantage function as given in
Equation (4) require $\bar{r}_{t+1}$ which is not available to each agent
$i\in N$. Therefore, we parameterize the reward function $\bar{R}(s,a)$ used
in the critic update as well. Let $\bar{R}(s,a)$ be approximated using a
linear function as $\bar{R}(s,a;\lambda)=\lambda^{\top}f(s,a)$, where
$f(s,a)=[f_{1}(s,a),\dots,f_{M}(s,a)]^{\top}\in\mathbb{R}^{M},~{}M<<|\mathcal{S}||\mathcal{A}|$
are the features associated with state action pair $(s,a)$. To obtain the
estimate of $\bar{R}(s,a)$ we use the following least square minimization

$min_{\lambda}~{}\sum_{s\in\mathcal{S},a\in\mathcal{A}}\tilde{d}_{\theta}(s,a)[\bar{R}(s,a)-\bar{R}(s,a;\lambda)]^{2},$

where $\bar{R}(s,a):=\frac{1}{n}\sum_{i\in{N}}R^{i}(s,a)$, and
$\tilde{d}_{\theta}(s,a)=d_{\theta}(s)\cdot\pi_{\theta}(s,a)$. The above
optimization problem can be equivalently characterized as

$min_{\lambda}~{}\sum_{i\in{N}}\sum_{s\in\mathcal{S},a\in\mathcal{A}}\tilde{d}_{\theta}(s,a)[{R}^{i}(s,a)-\bar{R}(s,a;\lambda)]^{2},$

as both the optimization problems have the same stationary points. For more
details see Appendix A.2.

Taking first order derivative with respect to $\lambda$ implies that we should
also do the following as a part of critic update:

$\tilde{\lambda}^{i}_{t}=\lambda^{i}_{t}+\beta_{v,t}\cdot[r^{i}_{t+1}-\bar{R}_{t}(\lambda^{i}_{t})]\cdot\nabla_{\lambda}\bar{R}_{t}(\lambda^{i}_{t});~{}~{}\lambda^{i}_{t+1}=\sum_{j\in{N}}c_{t}(i,j)\tilde{\lambda}^{j}_{t},$
(7)

where $\bar{R}_{t}(\lambda^{i}_{t})$ is the linear function approximation of
the global reward $\bar{R}_{t}(s_{t},a_{t})$ by agent $i\in N$ at time $t$,
i.e., $\bar{R}_{t}(\lambda^{i}_{t})=\lambda_{t}^{i^{\top}}f(s_{t},a_{t})$. The
TD error with parameterized reward, $\bar{R}_{t}(\cdot)$ is given by
$\tilde{\delta}^{i}_{t}:=\bar{R}_{t}(\lambda^{i}_{t})-\mu^{i}_{t}+V_{t+1}(v^{i}_{t})-V_{t}(v^{i}_{t})$.
Note that each agent $i\in N$ knows its local reward function
$r^{i}_{t+1}(s_{t},a_{t})$, but at the same time he/she also seeks to get some
information about the global reward, $\bar{r}_{t+1}(s_{t},a_{t})$ because the
objective is to maximize the globally averaged reward function. Therefore, in
above Equation (7), each agent $i\in N$ uses $\bar{R}_{t}(\lambda^{i}_{t})$ as
an estimate of the global reward function. Each agent $i\in N$ then updates
the policy/actor parameters as

$\displaystyle\theta^{i}_{t+1}$ $\displaystyle=$
$\displaystyle\theta^{i}_{t}+\beta_{\theta,t}\cdot\tilde{\delta}^{i}_{t}\cdot\psi^{i}_{t},$
(8)

where $\beta_{\theta,t}>0$ is the actor step size. Note that we have used
$\tilde{\delta}^{i}_{t}\cdot\psi^{i}_{t}$ instead of
$\nabla_{\theta^{i}}J(\theta)$ in the actor update. However,
$\tilde{\delta}^{i}_{t}\cdot\psi^{i}_{t}$ may not be an unbiased estimate of
the gradient of objective function $\nabla_{\theta^{i}}J(\theta)$. This
follows from the policy gradient Theorem for $\nabla_{\theta^{i}}J(\theta)$;
consider the following difference

$\displaystyle\mathbb{E}_{s_{t}\sim
d_{\theta},a_{t}\sim\pi_{\theta}}[\tilde{\delta}^{i}_{t}\cdot\psi^{i}_{t}]-\nabla_{\theta^{i}}J(\theta)$
$\displaystyle=$ $\displaystyle\mathbb{E}_{s_{t}\sim
d_{\theta},a_{t}\sim\pi_{\theta}}[(\bar{R}_{t}(\lambda^{i}_{t})-\mu^{i}_{t}+V_{t+1}(v^{i}_{t})-V_{t}(v^{i}_{t}))\cdot\psi^{i}_{t}]-\mathbb{E}_{s_{t}\sim
d_{\theta},a_{t}\sim\pi_{\theta}}[(\bar{R}(s_{t},a_{t})-\mu^{i}_{t}+V_{t+1}(v^{i}_{t})-V(s_{t}))\cdot\psi^{i}_{t}]$
$\displaystyle=$ $\displaystyle\mathbb{E}_{s_{t}\sim
d_{\theta},a_{t}\sim\pi_{\theta}}[(\bar{R}_{t}(\lambda^{i}_{t})-\bar{R}(s_{t},a_{t}))\cdot\psi^{i}_{t}]+\mathbb{E}_{s_{t}\sim
d_{\theta}}[(V_{\theta}(s_{t})-V_{t}(v^{i}_{t}))\cdot\psi^{i}_{t}]$

This implies,

$\mathbb{E}_{s_{t}\sim
d_{\theta},a_{t}\sim\pi_{\theta}}[\tilde{\delta}^{i}_{t}\cdot\psi^{i}_{t}]=\nabla_{\theta^{i}}J(\theta)+b~{}~{}where,$
(9)

$b=\mathbb{E}_{s_{t}\sim
d_{\theta},a_{t}\sim\pi_{\theta}}[(\bar{R}_{t}(\lambda^{i}_{t})-\bar{R}(s_{t},a_{t}))\cdot\psi^{i}_{t}]+\mathbb{E}_{s_{t}\sim
d_{\theta}}[(V_{\theta}(s_{t})-V_{t}(v^{i}_{t}))\cdot\psi^{i}_{t}]$ is the
bias term. The bias captures the sum of the expected linear approximation
errors in the reward and value functions. If these approximation errors are
small, the convergence point of the ODE corresponding to the actor update (as
given in Section 4) is close to the local optima of $J(\theta)$. In fact, in
Section 4, we show that the actor parameters converge to asymptotically stable
equilibrium set of ODEs corresponding to the actor updates, hence possibly
nullifying the bias. To prove the convergence of actor-critic algorithm we
require the following conditions on the step sizes
$\beta_{v,t},\beta_{\theta,t}$

$(a)~{}\sum_{t}\beta_{v,t}=\sum_{t}\beta_{\theta,t}=\infty;~{}~{}~{}(b)~{}\sum_{t}\left(\beta_{v,t}^{2}+\beta_{\theta,t}^{2}\right)<\infty,$
(10)

moreover, $\beta_{\theta,t}=o(\beta_{v,t})$, and
$lim_{t}\frac{\beta_{v,t+1}}{\beta_{v,t}}=1$, i.e., critic update is made at
the faster time scale than the actor update. Condition in (a) ensures that the
discrete time steps $\beta_{v,t},\beta_{\theta,t}$ used in the critic and
actor steps do cover the entire time axis while retaining
$\beta_{v,t},\beta_{\theta,t}\rightarrow 0$. We also require the error due to
the estimates used in critic and the actor updates are asymptotically
negligible almost surely. So, condition in (b) asymptotically suppresses the
variance in the estimates [Borkar, 2009]; see [Thoppe and Borkar, 2019] for
some recent developments that do away with this requirement.

The multi-agent actor-critic scheme given in the MAAC algorithm uses standard
(or vanilla) gradients. However, they are most useful for reward functions
that have single optima and whose gradients are isotropic in magnitude for any
direction away from its optimum [Amari and Douglas, 1998]. None of these
properties are valid in typical reinforcement learning environments. Apart
from this, the performance of standard gradient-based reinforcement learning
algorithms depends on the coordinate system used to define the objective
function. It is one of the most significant drawbacks of the standard gradient
[Kakade, 2001, Bagnell and Schneider, 2003].

Moreover, in many applications such as robotics, the state space contains
angles, so the state space has manifolds (curvatures). The objective function
will then be defined in that curved space, making the policy gradients methods
inefficient. We thus require a method that incorporates the knowledge about
curvature of the space into the gradient. The natural gradients are the most
“natural” choices in such cases. The following section describes the natural
gradients and uses them along with the policy gradient theorem in the multi-
agent setup.

###  2.1 Natural gradients and the Fisher information matrix

Recall, the objective function, $J(\cdot)$ given in Equation (1) is
parameterized by $\theta$. For the single agent actor-critic methods involving
natural gradients, $\widetilde{\nabla}J(\theta)$, authors in [Peters et al.,
2003, Bhatnagar et al., 2009a] have defined it via Fisher information matrix,
$G(\theta)$ and standard gradients, $\nabla J(\theta)$ as

$\widetilde{\nabla}_{\theta}J(\theta)=G(\theta)^{-1}\nabla_{\theta}J(\theta),$
(11)

where $G(\theta)$ is a positive definite matrix defined as

$G(\theta):=\mathbb{E}_{s\sim
d_{\theta},a\sim\pi_{\theta}}[\nabla_{\theta}\log\pi_{\theta}(s,a)\nabla_{\theta}\log\pi_{\theta}(s,a)^{\top}].$
(12)

The above Fisher information matrix is the covariance of the score function.
It can also be interpreted via KL
divergence111https://towardsdatascience.com/natural-gradient-ce454b3dcdfa
between the policy $\pi(\cdot,\cdot)$ parameterize at $\theta$ and
$\theta+\Delta\theta$ as below [Martens, 2020, Ratliff, 2013],

$KL(\pi_{\theta}(\cdot,\cdot)||\pi_{\theta+\Delta\theta}(\cdot,\cdot))\approx\frac{1}{2}\Delta\theta^{\top}\cdot
G(\theta)\cdot\Delta\theta.$ (13)

The above expression is obtained from the second-order Taylor expansion of
$\log\pi_{\theta+\Delta\theta}(s,a)$, and using the fact that the sum of the
probabilities is one. In above, the right-hand term is a quadratic involving
positive definite matrix $G(\theta)$, and hence $G(\theta)$ approximately
captures the curvature of the KL divergence between policy distributions at
$\theta$ and $\theta+\Delta\theta$.

We now relate the Fisher information matrix, $G(\theta)$ to the objective
function, $J(\theta)$.

######  Lemma 1.

The gradient of the KL divergence between two consecutive policies is
approximately proportional to the gradient of the objective function, i.e.,

$\nabla
KL(\pi_{\theta_{t}}(\cdot,\cdot)||\pi_{\theta_{t}+\Delta\theta_{t}}(\cdot,\cdot))\propto\nabla
J(\theta_{t}).$

###### Proof.

From Equation (13), the KL divergence is a function of the Fisher information
matrix and delta change in the policy parameters. We find the optimal step-
size $\Delta\theta_{t}^{\star}$ via the following optimization problem

$\displaystyle\Delta\theta_{t}^{\star}=$
$\displaystyle~{}argmax_{\Delta\theta_{t}}~{}J(\theta_{t}+\Delta\theta_{t})$
$\displaystyle
s.t.~{}~{}KL(\pi_{\theta_{t}}(\cdot,\cdot)||\pi_{\theta_{t}+\Delta\theta_{t}}(\cdot,\cdot))=c.$

Writing the Lagrange $\mathcal{L}(\theta_{t}+\Delta\theta_{t};\rho_{t})$
(where $\rho_{t}$ is the Lagrangian multiplier) of the above optimization
problem and using the first order Taylor approximation along with the
approximation of the KL divergence as given in Equation (13), we have

$\displaystyle\Delta\theta_{t}^{\star}$ $\displaystyle=$ $\displaystyle
argmax_{\Delta\theta_{t}}~{}J(\theta_{t}+\Delta\theta_{t})+\rho_{t}(KL(\pi_{\theta_{t}}(\cdot,\cdot)||\pi_{\theta_{t}+\Delta\theta_{t}}(\cdot,\cdot))-c),$
$\displaystyle\approx$ $\displaystyle
argmax_{\Delta\theta_{t}}~{}J(\theta_{t})+\Delta\theta_{t}^{\top}\nabla_{\theta}J(\theta_{t})+\frac{1}{2}\cdot\rho_{t}\cdot\Delta\theta_{t}^{\top}\cdot
G(\theta_{t})\cdot\Delta\theta_{t}-\rho_{t}c.$

Setting the derivative (w.r.t. $\Delta\theta_{t}$) of above Lagrangian to
zero, we have

$\nabla_{\theta}J(\theta_{t})+\rho_{t}\cdot\Delta\theta_{t}^{\star{{}^{\top}}}\cdot
G(\theta_{t})=0~{}\implies~{}\Delta\theta_{t}^{\star}=-\frac{1}{\rho_{t}}G(\theta_{t})^{-1}\nabla
J(\theta_{t}),$ (14)

i.e., upto the factor of $-\frac{1}{\rho_{t}}$, we get an optimal step-size in
terms of the standard gradients and the Fisher information matrix at point
$\theta_{t}$. Moreover, from Equations (13) and (14) we have,

$\nabla
KL(\pi_{\theta_{t}}(\cdot,\cdot)||\pi_{\theta_{t}+\Delta\theta_{t}}(\cdot,\cdot))\approx
G(\theta_{t})\Delta\theta_{t}^{\star};~{}~{}~{}and~{}~{}~{}G(\theta_{t})\Delta\theta_{t}^{\star}=-\frac{1}{\rho_{t}}\nabla
J(\theta_{t}).$ (15)

and hence,

$\nabla
KL(\pi_{\theta_{t}}(\cdot,\cdot)||\pi_{\theta_{t}+\Delta\theta_{t}}(\cdot,\cdot))\approx-\frac{1}{\rho_{t}}\nabla
J(\theta_{t}).$ (16)

This ends the proof. ∎

The above lemma relates the gradient of the objective function to the gradient
of KL divergence between the policies separated by $\Delta\theta_{t}$. The
above equation provides a valuable observation because we can adjust the
updates (of actor parameter $\theta_{t}$) just by moving in the prediction
space of the parameterized policy distributions. Thus, those MAN algorithms
discussed later that rely on Fisher information matrix $G(\cdot)$ _implicitly_
use the above representation for $\nabla J(\cdot)$. This again justifies the
natural gradients as given in Equation (11). We recall these aspects in
Section 3.6 for the Boltzmann policies.

###  2.2 Multi-agent natural policy gradient theorem and rank-one update of
$G_{t+1}^{i^{-1}}$

In this section, we provide the details of natural policy gradient methods and
the Fisher information matrix in the multi-agent setup. Similar to Equation
(11), in multi-agent setup the natural gradient of the objective function is

$\widetilde{\nabla}_{\theta^{i}}J(\theta)=G(\theta^{i})^{-1}\nabla_{\theta^{i}}J(\theta),~{}\forall~{}i\in
N,$ (17)

where $G(\theta^{i}):=\mathbb{E}_{s\sim
d_{\theta},a\sim\pi_{\theta}}[\nabla_{\theta^{i}}\log\pi^{i}_{\theta^{i}}(s,a^{i})\nabla_{\theta^{i}}\log\pi^{i}_{\theta^{i}}(s,a^{i})^{\top}]$
is again a positive definite matrix for each agent $i\in N$. We now present
the policy gradient theorem for multi-agent setup involving the natural
gradients.

######  Theorem 2 (Policy gradient theorem for MARL with natural gradients).

Under assumption X. 1, the natural gradient of $J(\theta)$ with respect to
$\theta^{i}$ for each $i\in N$ is given by

$\displaystyle\widetilde{\nabla}_{\theta^{i}}J(\theta)$ $\displaystyle=$
$\displaystyle G(\theta^{i})^{-1}\mathbb{E}_{s\sim
d_{\theta},a\sim\pi_{\theta}}[\nabla_{\theta^{i}}\log\pi^{i}_{\theta^{i}}(s,a^{i})\cdot
A_{\theta}(s,a)]$ $\displaystyle=$ $\displaystyle
G(\theta^{i})^{-1}\mathbb{E}_{s\sim
d_{\theta},a\sim\pi_{\theta}}[\nabla_{\theta^{i}}\log\pi^{i}_{\theta^{i}}(s,a^{i})\cdot
A^{i}_{\theta}(s,a)].$

###### Proof.

The proof follows from the multi-agent policy gradient Theorem 1 and using
Equation (17), i.e.,
$\widetilde{\nabla}_{\theta^{i}}J(\theta)=G(\theta^{i})^{-1}\nabla_{\theta^{i}}J(\theta),~{}~{}\forall
i\in N$. ∎

It is well known that inverting a Fisher information matrix is computationally
heavy [Kakade, 2001, Peters and Schaal, 2008]. Whereas, in our natural
gradient-based multi-agent actor-critic methods we require the inverse of
Fisher information matrix $G(\theta^{i})^{-1},~{}~{}\forall~{}i\in N$. To this
end, we derive the procedure for recursively estimating the
$G(\theta^{i})^{-1}$ for each agent $i\in N$ at the faster time scale
[Bhatnagar et al., 2009a]. Let $G^{i^{-1}}_{t+1},t\geq 0$ be the $t$-th
estimate of $G(\theta^{i})^{-1}$. Consider the sample averages at time $t\geq
0$,

$G_{t+1}^{i}=\frac{1}{t+1}\sum_{l=0}^{t}\psi^{i}_{l}\psi_{l}^{i^{\top}},$

where $\psi^{i}_{l}=\psi^{i}_{l}(s_{l},a^{i}_{l})$ is the score function of
agent $i\in N$ at time $l$. Thus, $G^{i}_{t+1}$ will be recursively obtained
as

$G^{i}_{t+1}=\left(1-\frac{1}{t+1}\right)G^{i}_{t}+\frac{1}{t+1}\psi^{i}_{t}\psi_{t}^{i^{\top}}.$

More generally, one can consider the following recursion

$G^{i}_{t+1}=(1-\beta_{v,t})G^{i}_{t}+\beta_{v,t}\psi^{i}_{t}\psi_{t}^{i^{\top}},$
(18)

where $\beta_{v,t}>0$ is the step size as earlier. Using the idea of
stochastic convergence, if $\theta^{i}$ is held constant, $G^{i}_{t+1}$
converge to $G(\theta^{i})$ with probability one. For all $i\in N$, we write
the recursion for the Fisher information matrix inverse, $G_{t+1}^{i^{-1}}$
using Sherman-Morrison matrix inversion [Sherman and Morrison, 1950] (see also
[Bhatnagar et al., 2009a]) as follows

$G_{t+1}^{i^{-1}}=\frac{1}{1-\beta_{v,t}}\left[G_{t}^{i^{-1}}-\beta_{v,t}\frac{(G_{t}^{i^{-1}}\psi^{i}_{t})(G_{t}^{i^{-1}}\psi_{t}^{i})^{\top}}{1-\beta_{v,t}+\beta_{v,t}\psi_{t}^{i^{\top}}G_{t}^{i^{-1}}\psi_{t}^{i}}\right].$
(19)

The Sherman-Morrison update is done at a faster time scale $\beta_{v,t}>0$, to
ensure that Fisher information inverse estimates are available before actor
update.

The following section provides three multi-agent natural actor-critic (MAN) RL
algorithms involving consensus matrices. Moreover, we will also investigate
the relations among these algorithms and their effect on the quality of the
local optima they attain.

##  3 Multi-agent natural actor-critic (MAN) algorithms

This section provides three multi-agent natural actor-critic (MAN)
reinforcement learning algorithms. Two of the three MAN algorithms explicitly
use the Fisher information matrix inverse, whereas one uses the linear
function approximation of the advantage parameters.

###  3.1 FI-MAN: Fisher information based multi-agent natural actor-critic
algorithm

Our first multi-agent natural actor-critic algorithm uses the fact that
natural gradients can be obtained via the Fisher information matrix and the
standard gradients as given in Equation (17). The updates of objective
function estimate, critic, and the rewards parameters in FI-MAN algorithm are
the same as given in Equations (5), (6), and (7), respectively. The major
difference between the MAAC and the FI-MAN algorithm is in the actor update.
FI-MAN algorithm uses the following actor update

$\theta^{i}_{t+1}\leftarrow\theta^{i}_{t}+\beta_{\theta,t}\cdot
G_{t}^{i^{-1}}\cdot\tilde{\delta}^{i}_{t}\cdot\psi^{i}_{t},~{}~{}\forall~{}i\in
N,$ (20)

where $\beta_{v,t}$ and $\beta_{\theta,t}$ are the critic and the actor step-
sizes respectively. The pseudo code of the algorithm is given in FI-MAN
algorithm.

Input: Initial values of
$\mu^{i}_{0},\tilde{\mu}^{i}_{0},v^{i}_{0},\tilde{v}^{i}_{0},\lambda^{i}_{0},\tilde{\lambda}^{i}_{0},\theta^{i}_{0},G_{0}^{i^{-1}},~{}\forall~{}i\in{N}$;
initial state $s_{0}$; stepsizes $\\{\beta_{v,t}\\}_{t\geq
0},\\{\beta_{\theta,t}\\}_{t\geq 0}$.

Each agent $i$ implements $a^{i}_{0}\sim\pi_{\theta^{i}_{0}}(s_{0},\cdot)$.

Initialize the step counter $t\leftarrow 0$.

repeat

for  _all $i\in N$_ do

Observe state $s_{t+1}$, and reward $r^{i}_{t+1}$.

Update:
$\tilde{\mu}^{i}_{t}\leftarrow(1-\beta_{v,t})\cdot\mu^{i}_{t}+\beta_{v,t}\cdot
r^{i}_{t+1}$.

$\tilde{\lambda}^{i}_{t}\leftarrow\lambda^{i}_{t}+\beta_{v,t}\cdot[r^{i}_{t+1}-\bar{R}_{t}(\lambda^{i}_{t})]\cdot\nabla_{\lambda}\bar{R}_{t}(\lambda^{i}_{t})$,
where $\bar{R}_{t}(\lambda^{i}_{t})=\lambda^{i^{\top}}_{t}f(s_{t},a_{t})$.

Update: $\delta^{i}_{t}\leftarrow
r^{i}_{t+1}-\mu^{i}_{t}+V_{t+1}(v^{i}_{t})-V_{t}(v^{i}_{t})$, where
$V_{t+1}(v^{i}_{t})=v^{i^{\top}}_{t}\varphi(s_{t+1})$.

Critic Step: $\tilde{v}^{i}_{t}\leftarrow
v^{i}_{t}+\beta_{v,t}\cdot\delta^{i}_{t}\cdot\nabla_{v}V_{t}(v^{i}_{t})$,

Update:
$\tilde{\delta}^{i}_{t}\leftarrow\bar{R}_{t}(\lambda^{i}_{t})-\mu^{i}_{t}+V_{t+1}(v^{i}_{t})-V_{t}(v^{i}_{t})$;
$\psi^{i}_{t}\leftarrow\nabla_{\theta^{i}}\log\pi^{i}_{\theta^{i}_{t}}(s_{t},a^{i}_{t})$.

Actor Step: $\theta^{i}_{t+1}\leftarrow\theta^{i}_{t}+\beta_{\theta,t}\cdot
G_{t}^{i^{-1}}\cdot\tilde{\delta}^{i}_{t}\cdot\psi^{i}_{t}$.

Send $\tilde{\mu}^{i}_{t},\tilde{\lambda}^{i}_{t},\tilde{v}^{i}_{t}$ to the
neighbors over $\mathcal{G}_{t}$.

for  _all $i\in{N}$_ do

Consensus Update:
$\mu^{i}_{t+1}\leftarrow\sum_{j\in{N}}c_{t}(i,j)\tilde{\mu}^{j}_{t}$;

$\lambda^{i}_{t+1}\leftarrow\sum_{j\in{N}}c_{t}(i,j)\tilde{\lambda}^{j}_{t};~{}~{}v^{i}_{t+1}\leftarrow\sum_{j\in{N}}c_{t}(i,j)\tilde{v}^{j}_{t}.$

Fisher Update:
$G_{t+1}^{i^{-1}}\leftarrow\frac{1}{1-\beta_{v,t}}\left[G_{t}^{i^{-1}}-\beta_{v,t}\frac{(G_{t}^{i^{-1}}\psi^{i}_{t})(G_{t}^{i^{-1}}\psi^{i}_{t})^{\top}}{1-\beta_{v,t}+\beta_{v,t}\psi_{t}^{i^{\top}}G_{t}^{i^{-1}}\psi_{t}^{i}}\right].$

Update: $t\leftarrow t+1$.

until  _Convergence_ ;

FI-MAN 1 Fisher information based multi-agent natural actor critic

Note that the FI-MAN algorithm explicitly uses $G^{i^{-1}}_{t}$ in the actor
update. Though the Fisher information inverse matrix is updated according to
the Sherman-Morrison inverse at a faster time scale, it may be better to avoid
explicit use of the Fisher inverse in the actor update. To this end, we use
the linear function approximation of the advantage function. This leads to the
AP-MAN algorithm, i.e., advantage parameters based multi-agent natural actor-
critic algorithm.

###  3.2 AP-MAN: Advantage parameters based multi-agent natural actor critic
algorithm

Consider the local advantage function
$A^{i}(s,a^{i}):\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R}$ for each
agent $i\in N$. Let the local advantage function $A^{i}(s,a^{i})$ be linearly
approximated as $A^{i}(s,a^{i};w^{i}):=w^{i^{\top}}\psi^{i}(s,a^{i})$, where
$\psi^{i}(s,a^{i})=\nabla_{\theta^{i}}\log\pi^{i}_{\theta^{i}}(s,a^{i})$ are
the compatible features, and $w^{i}\in\mathbb{R}^{m_{i}}$ are the advantage
function parameters. Recall, the same $\psi^{i}(s,a^{i})$ was used to
represent the score function in the policy gradient theorem, Theorem 1.
However, it also serves as the compatible feature while approximating the
advantage function as it satisfy the compatibility condition in the policy
gradient theorem with linear function approximations (Theorem 2 [Sutton et
al., 1999]). The compatibility condition as given in [Sutton et al., 1999] is
for single agent however, we are using it explicitly for each agent $i\in N$.
Whenever there is no confusion, we write $\psi^{i}$ instead of
$\psi^{i}(s,a^{i})$, to save space. We can tune $w^{i}$ in such a way that the
estimate of least squared error in linear function approximation of advantage
function is minimized, i.e.,

$\mathcal{E}^{\pi_{\theta}}(w^{i})=\frac{1}{2}\sum_{s\in\mathcal{S},a^{i}\in\mathcal{A}^{i}}\tilde{d}_{\theta}(s,a^{i})[w^{i^{\top}}\psi^{i}(s,a^{i})-A^{i}(s,a^{i})]^{2},$
(21)

is minimized. Here
$\tilde{d}_{\theta}(s,a^{i})=d_{\theta}(s)\cdot\pi^{i}_{\theta^{i}}(s,a^{i})$
as defined earlier. Taking the derivative of Equation (21), we have
$\nabla_{w^{i}}\mathcal{E}^{\pi_{\theta}}(w^{i})=\sum_{s\in\mathcal{S},a^{i}\in\mathcal{A}^{i}}\tilde{d}_{\theta}(s,a^{i})[w^{i^{\top}}\psi^{i}-A^{i}(s,a^{i})]\psi^{i}$.
Noting that parameterized TD error $\tilde{\delta}^{i}_{t}$ is an unbiased
estimate of the local advantage function $A^{i}(s,a^{i})$, we will use the
following estimate of $\nabla_{w^{i}}\mathcal{E}^{\pi_{\theta}}(w^{i})$,

$\widehat{\nabla_{w^{i}}}\mathcal{E}^{\pi_{\theta}}(w^{i}_{t})=\psi^{i}_{t}\psi^{i^{\top}}_{t}w^{i}_{t}-\tilde{\delta}^{i}_{t}\psi^{i}_{t}.$

Hence the update of advantage parameter $w^{i}$ in the AP-MAN algorithm is

$\displaystyle w^{i}_{t+1}$ $\displaystyle=$ $\displaystyle
w^{i}_{t}-\beta_{v,t}\widehat{\nabla_{w^{i}}}\mathcal{E}^{\pi_{\theta}}(w^{i}_{t})$
(22) $\displaystyle=$
$\displaystyle(I-\beta_{v,t}\psi^{i}_{t}\psi^{i^{\top}}_{t})w^{i}_{t}+\beta_{v,t}\tilde{\delta}^{i}_{t}\psi^{i}_{t}.$

The updates of the objective function estimate, critic, and reward parameters
in the AP-MAN algorithm are the same as given in Equations (5), (6), and (7),
respectively. Additionally, in the critic step we update the advantage
parameters as given in Equation (22). For single agent RL with natural
gradients, [Peters and Schaal, 2008, Peters et al., 2003] show that
$\widetilde{\nabla}_{\theta}J(\theta)=w$. In MARL with natural gradient, we
separately verified and hence use
$\widetilde{\nabla}_{\theta^{i}}J(\theta)=w^{i}$ for each agent $i\in N$ in
the actor update of AP-MAN algorithm. The AP-MAN actor-critic algorithm thus
uses the following actor update

$\theta^{i}_{t+1}\leftarrow\theta^{i}_{t}+\beta_{\theta,t}\cdot w^{i}_{t+1}.$
(23)

The algorithm’s pseudo-code involving advantage parameters is given in the AP-
MAN algorithm.

Input: Initial values of
$\mu^{i}_{0},\tilde{\mu}^{i}_{0},v^{i}_{0},\tilde{v}^{i}_{0},\lambda^{i}_{0},\tilde{\lambda}^{i}_{0},\theta^{i}_{0},w^{i}_{0},~{}\forall
i\in{N}$; initial state $s_{0}$; stepsizes $\\{\beta_{v,t}\\}_{t\geq
0},\\{\beta_{\theta,t}\\}_{t\geq 0}.$

Each agent $i$ implements $a^{i}_{0}\sim\pi_{\theta^{i}_{0}}(s_{0},\cdot).$

Initialize the step counter $t\leftarrow 0.$

repeat

for  _all $i\in{N}$_ do

Observe state $s_{t+1}$, and reward $r^{i}_{t+1}.$

Update:
$\tilde{\mu}^{i}_{t}\leftarrow(1-\beta_{v,t})\cdot\mu^{i}_{t}+\beta_{v,t}\cdot
r^{i}_{t+1}.$

$\tilde{\lambda}^{i}_{t}\leftarrow\lambda^{i}_{t}+\beta_{v,t}\cdot[r^{i}_{t+1}-\bar{R}_{t}(\lambda^{i}_{t})]\cdot\nabla_{\lambda}\bar{R}_{t}(\lambda^{i}_{t})$,
where $\bar{R}_{t}(\lambda^{i}_{t})=\lambda^{i^{\top}}_{t}f(s_{t},a_{t})$.

Update: $\delta^{i}_{t}\leftarrow
r^{i}_{t+1}-\mu^{i}_{t}+V_{t+1}(v^{i}_{t})-V_{t}(v^{i}_{t})$, where
$V_{t+1}(v^{i}_{t})=v^{i^{\top}}_{t}\varphi(s_{t+1})$.

Critic Step: $\tilde{v}^{i}_{t}\leftarrow
v^{i}_{t}+\beta_{v,t}\cdot\delta^{i}_{t}\cdot\nabla_{v}V_{t}(v^{i}_{t}).$

Update:
$\tilde{\delta}^{i}_{t}\leftarrow\bar{R}_{t}(\lambda^{i}_{t})-\mu^{i}_{t}+V_{t+1}(v^{i}_{t})-V_{t}(v^{i}_{t})$;
$\psi^{i}_{t}\leftarrow\nabla_{\theta^{i}}\log\pi^{i}_{\theta^{i}_{t}}(s_{t},a^{i}_{t}).$

Update:
${w}^{i}_{t+1}\leftarrow(I-\beta_{v,t}\psi^{i}_{t}\psi^{i^{\top}}_{t})w^{i}_{t}+\beta_{v,t}\tilde{\delta}^{i}_{t}\psi^{i}_{t}.$

Actor Step: $\theta^{i}_{t+1}\leftarrow\theta^{i}_{t}+\beta_{\theta,t}\cdot
w^{i}_{t+1}.$

Send $\tilde{\mu}^{i}_{t},\tilde{\lambda}^{i}_{t},\tilde{v}^{i}_{t}$ to the
neighbors over $\mathcal{G}_{t}$.

for  _all $i\in{N}$_ do

Consensus Update:
$\mu^{i}_{t+1}\leftarrow\sum_{j\in{N}}c_{t}(i,j)\tilde{\mu}^{j}_{t}$;

$\lambda^{i}_{t+1}\leftarrow\sum_{j\in{N}}c_{t}(i,j)\tilde{\lambda}^{j}_{t};~{}~{}v^{i}_{t+1}\leftarrow\sum_{j\in{N}}c_{t}(i,j)\tilde{v}^{j}_{t}.$

Update: $t\leftarrow t+1$.

until  _Convergence_ ;

AP-MAN 2 Advantage parameters based multi-agent natural actor critic

######  Remark 1.

We want to emphasize that the AP-MAN algorithm does not explicitly use the
inverse of Fisher information matrix, $G(\theta^{i})^{-1}$ in the actor update
(as also in [Bhatnagar et al., 2009a]); hence it requires fewer computations.
However, it involves the linear function approximation of the advantage
function, as given in Equation (22), that itself requires
$\psi^{i}_{t}\psi^{i^{\top}}_{t}$ which is an unbiased estimate of the Fisher
information matrix (see Equation (12)). We will see later in Section 3.4 that
the performance of the AP-MAN algorithm is almost the same as the MAAC
algorithm. We empirically verify this observation in the computational
experiments in Section 5.

######  Remark 2.

The advantage function is a linear combination of $Q_{\theta}(s,a)$ and
$V_{\theta}(s)$; therefore, the linear function approximation of the advantage
function alone enjoys the benefit of approximating the $Q_{\theta}(s,a)$ or
$V_{\theta}(s)$. Moreover, MAAC uses the linear function approximation of
$V_{\theta}(s)$; hence, we expect the behavior of AP-MAN to be similar to that
of MAAC; this comes out in our computational experiments in Section 5.

The FI-MAN algorithm is based solely on the Fisher information matrix and the
AP-MAN algorithm on the advantage function approximation. Our next algorithm,
FIAP-MAN algorithm, i.e., Fisher information and advantage parameter based
multi-agent natural actor-critic algorithm, combine them in a certain way. We
see the benefits of this combination in Sections 3.4 and 5.1. In particular,
in Section 5.1 we illustrate these benefits in 2 arrival distributions in the
traffic network congestion model.

###  3.3 FIAP-MAN: Fisher information and advantage parameter based multi-
agent natural actor-critic algorithm

Recall in Section 3.2, for each agent $i\in N$, the local advantage function
$A^{i}(s,a^{i}):\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R}$ has linear
function approximation $A^{i}(s,a^{i};w^{i})=w^{i^{\top}}\psi^{i}(s,a^{i})$,
where $\psi^{i}(s,a^{i})$ are the compatible features as before, and
${\color[rgb]{0,0,0}w^{i}\in\mathbb{R}^{m_{i}}}$ are the advantage function
parameters. In AP-MAN algorithm the Fisher inverse $G(\theta^{i})^{-1}$ is not
estimated explicitly, however in FIAP-MAN algorithm we explicitly estimate
$G(\theta^{i})^{-1}$ along with the advantage parameters and hence use the
following estimate of $\nabla_{w^{i}}\mathcal{E}^{\pi_{\theta}}(w^{i})$,

$\widehat{\nabla_{w^{i}}}\mathcal{E}^{\pi_{\theta}}(w^{i}_{t})=G^{i^{-1}}_{t}(\psi^{i}_{t}\psi^{i^{\top}}_{t}w^{i}_{t}-\tilde{\delta}^{i}_{t}\psi^{i}_{t}),~{}~{}\forall~{}i\in
N.$

The update of advantage parameters, $w^{i}$ along with the critic update in
the FIAP-MAN algorithm is given by

$\displaystyle w^{i}_{t+1}$ $\displaystyle=$ $\displaystyle
w^{i}_{t}-\beta_{v,t}\widehat{\nabla_{w^{i}}}\mathcal{E}^{\pi_{\theta}}(w^{i}_{t})$
(24) $\displaystyle=$ $\displaystyle
w^{i}_{t}-\beta_{v,t}G^{i^{-1}}_{t}(\psi^{i}_{t}\psi^{i^{\top}}_{t}w^{i}_{t}-\tilde{\delta}^{i}_{t}\psi^{i}_{t})$
$\displaystyle=$
$\displaystyle(1-\beta_{v,t})w^{i}_{t}+\beta_{v,t}G^{i^{-1}}_{t}\tilde{\delta}^{i}_{t}\psi^{i}_{t}.$

######  Remark 3.

Note that we take
$G^{i^{-1}}_{t}\psi^{i}_{t}\psi^{i^{\top}}_{t}=I,~{}\forall~{}i\in N$, though
$G_{t+1}=\frac{1}{t+1}\sum_{l=0}^{t}\psi_{l}{\psi_{l}}^{\top}$. A similar
approximation is also implicitly made in natural gradient algorithms in
[Bhatnagar et al., 2009a, Bhatnagar et al., 2009b] for single agent RL.
Convergence of FIAP-MAN algorithm with above approximate update in MARL is
given in Section 4. Later, we use these updates in our computations to
demonstrate their superior performance in multiple instances of traffic
network (Section 5).

The updates of the objective function estimate, critic, and reward parameters
in the FIAP-MAN algorithm are the same as given in Equations (5), (6), and (7)
respectively. Similar to the AP-MAN algorithm, the actor update in FIAP-MAN
algorithm is

$\theta^{i}_{t+1}\leftarrow\theta^{i}_{t}+\beta_{\theta,t}\cdot
w^{i}_{t+1},~{}~{}\forall~{}i\in N.$ (25)

Again for the same reason as in the AP-MAN algorithm, we use the advantage
parameters, $w^{i}$ instead of $\widetilde{\nabla}_{\theta^{i}}J(\theta)$,
i.e., $\widetilde{\nabla}_{\theta^{i}}J(\theta)=w^{i}$. The algorithm’s pseudo
code involving the Fisher information matrix inverse and advantage parameters
is given in FIAP-MAN algorithm.

Input: Initial values of
$\mu^{i}_{0},\tilde{\mu}^{i}_{0},v^{i}_{0},\tilde{v}^{i}_{0},\lambda^{i}_{0},\tilde{\lambda}^{i}_{0},\theta^{i}_{0},w^{i}_{0},G^{i^{-1}}_{0},~{}\forall~{}i\in{N}$;
initial state $s_{0}$; stepsizes $\\{\beta_{v,t}\\}_{t\geq
0},\\{\beta_{\theta,t}\\}_{t\geq 0}$.

Each agent $i$ implements $a^{i}_{0}\sim\pi_{\theta^{i}_{0}}(s_{0},\cdot)$.

Initialize the step counter $t\leftarrow 0$.

repeat

for  _all $i\in N$_ do

Observe state $s_{t+1}$, and reward $r^{i}_{t+1}$.

Update:
$\tilde{\mu}^{i}_{t}\leftarrow(1-\beta_{v,t})\cdot\mu^{i}_{t}+\beta_{v,t}\cdot
r^{i}_{t+1}$.

$\tilde{\lambda}^{i}_{t}\leftarrow\lambda^{i}_{t}+\beta_{v,t}\cdot[r^{i}_{t+1}-\bar{R}_{t}(\lambda^{i}_{t})]\cdot\nabla_{\lambda}\bar{R}_{t}(\lambda^{i}_{t})$,
where $\bar{R}_{t}(\lambda^{i}_{t})=\lambda^{i^{\top}}_{t}f(s_{t},a_{t})$.

Update: $\delta^{i}_{t}\leftarrow
r^{i}_{t+1}-\mu^{i}_{t}+V_{t+1}(v^{i}_{t})-V_{t}(v^{i}_{t})$, where
$V_{t+1}(v^{i}_{t})=v^{i^{\top}}_{t}\varphi(s_{t+1})$.

Critic Step: $\tilde{v}^{i}_{t}\leftarrow
v^{i}_{t}+\beta_{v,t}\cdot\delta^{i}_{t}\cdot\nabla_{v}V_{t}(v^{i}_{t})$.

Update:
$\tilde{\delta}^{i}_{t}\leftarrow\bar{R}_{t}(\lambda^{i}_{t})-\mu^{i}_{t}+V_{t+1}(v^{i}_{t})-V_{t}(v^{i}_{t})$;
$\psi^{i}_{t}\leftarrow\nabla_{\theta^{i}}\log\pi^{i}_{\theta^{i}_{t}}(s_{t},a^{i}_{t})$.

Update:
${w}^{i}_{t+1}\leftarrow(1-\beta_{v,t})w^{i}_{t}+\beta_{v,t}G^{i^{-1}}_{t}\tilde{\delta}^{i}_{t}\psi^{i}_{t}$.

Actor Step: $\theta^{i}_{t+1}\leftarrow\theta^{i}_{t}+\beta_{\theta,t}\cdot
w^{i}_{t+1}$.

Send $\tilde{\mu}^{i}_{t},\tilde{\lambda}^{i}_{t},\tilde{v}^{i}_{t}$ to the
neighbors over $\mathcal{G}_{t}$.

for  _all $i\in{N}$_ do

Consensus Update: $\mu^{i}_{t+1}\leftarrow\sum_{j\in
N}c_{t}(i,j)\tilde{\mu}^{j}_{t}$;

$\lambda^{i}_{t+1}\leftarrow\sum_{j\in
N}c_{t}(i,j)\tilde{\lambda}^{j}_{t};~{}~{}v^{i}_{t+1}\leftarrow\sum_{j\in
N}c_{t}(i,j)\tilde{v}^{j}_{t}$.

Fisher Update:
$G_{t+1}^{i^{-1}}\leftarrow\frac{1}{1-\beta_{v,t}}\left[G_{t}^{i^{-1}}-\beta_{v,t}\frac{(G_{t}^{i^{-1}}\psi^{i}_{t})(G_{t}^{i^{-1}}\psi^{i}_{t})^{\top}}{1-\beta_{v,t}+\beta_{v,t}\psi_{t}^{i^{\top}}G_{t}^{i^{-1}}\psi_{t}^{i}}\right]$.

Update: $t\leftarrow t+1$.

until  _Convergence_ ;

FIAP-MAN 3 Fisher information and advantage parameters based multi-agent
natural actor-critic

In the next section, we investigate the relation between the actor updates of
the MAAC and 3 MAN algorithms. In particular, we compare the actor parameters
of all the algorithms.

###  3.4 Relationship between actor updates in algorithms

Recall, the actor update for each agent $i\in N$ in FIAP-MAN algorithm is
$\theta^{i}_{t+1}=\theta^{i}_{t}+\beta_{\theta,t}w^{i}_{t+1}$, where
$w^{i}_{t+1}=(1-\beta_{v,t})w^{i}_{t}+\beta_{v,t}G^{i^{-1}}_{t}\tilde{\delta}^{i}_{t}\psi^{i}_{t}$.
Therefore, the actor update of FIAP-MAN algorithm is

$\displaystyle\theta^{i}_{t+1}$
$\displaystyle=\theta^{i}_{t}+\beta_{\theta,t}\left[(1-\beta_{v,t})w^{i}_{t}+\beta_{v,t}G^{i^{-1}}_{t}\tilde{\delta}^{i}_{t}\psi^{i}_{t}\right]$
(26)
$\displaystyle=\theta^{i}_{t}+\beta_{\theta,t}(1-\beta_{v,t})w^{i}_{t}+\beta_{v,t}\left\\{\beta_{\theta,t}G^{i^{-1}}_{t}\tilde{\delta}^{i}_{t}\psi^{i}_{t}\right\\}.$

The above update is almost the same as the actor update of the FI-MAN
algorithm with an additional term involving advantage parameters $w^{i}_{t}$.
However, the contribution of the second term is negligible after some time
$t$. Moreover, the third term in Equation (26) is a positive fraction of the
second term in the actor update of FI-MAN algorithm (Equation (20)).
Therefore, the actor parameters in FIAP-MAN and FI-MAN algorithms are almost
the same after time $t$. Hence, both the algorithms are expected to converge
almost to the same local optima.

Similarly, consider the actor update of the AP-MAN algorithm, i.e.,
$\theta^{i}_{t+1}=\theta^{i}_{t}+\beta_{\theta,t}w^{i}_{t+1}$, where
$w^{i}_{t+1}=(I-\beta_{v,t}\psi^{i}_{t}\psi^{i^{\top}}_{t})w^{i}_{t}+\beta_{v,t}\tilde{\delta}^{i}_{t}\psi^{i}_{t}$.
Therefore, the actor update of AP-MAN algorithm is

$\displaystyle\theta^{i}_{t+1}$
$\displaystyle=\theta^{i}_{t}+\beta_{\theta,t}\left[(I-\beta_{v,t}\psi^{i}_{t}\psi^{i^{\top}}_{t})w^{i}_{t}+\beta_{v,t}\tilde{\delta}^{i}_{t}\psi^{i}_{t}\right]$
(27)
$\displaystyle=\theta^{i}_{t}+\beta_{\theta,t}(I-\beta_{v,t}\psi^{i}_{t}\psi^{i^{\top}}_{t})w^{i}_{t}+\beta_{v,t}\left\\{\beta_{\theta,t}\tilde{\delta}^{i}_{t}\psi^{i}_{t}\right\\}.$

Again, the second term in the above equation is negligible after some time
$t$, and the third term of Equation (27) is a positive fraction of the second
term in the actor update of the MAAC algorithm (see Equation (8)). Hence the
actor update in the AP-MAN algorithm is almost the same as the MAAC algorithm;
therefore, AP-MAN and MAAC are expected to converge almost to the same local
optima.

###  3.5 Comparison of variants of MAN and MAAC algorithms

In this section, we show that under some conditions, a variant of the FI-MAN
algorithm dominates the corresponding variant of the MAAC algorithm for all
$t\geq t_{0}$, for some $t_{0}<\infty$. Using this, we derive the
corresponding result that compares the objective function $J(\cdot)$ among
these variants of algorithms. For this purpose, we propose a model to evaluate
the ‘efficiency’ of MAAC and FI-MAN algorithms in terms of their goal;
maximization of MARL objective function, $J(\theta)$. This comparison exploits
the intrinsic property of the Fisher information matrix $G(\theta)$ (Lemma 2,
an uniform upper bound on its minimum eigenvalue).

Let $\theta^{M}_{t}$ and $\theta^{N}_{t}$ be the actor parameters in MAAC and
FI-MAN algorithms, respectively. Recall the actor updates in MAAC and FI-MAN
algorithms were:

$\textbf{MAAC:}~{}\theta^{M}_{t+1}=\theta^{M}_{t}+\beta_{\theta,t}\tilde{\delta}_{t}\cdot\psi_{t};\hskip
5.69054pt\textbf{FI-
MAN:}~{}{\theta}^{N}_{t+1}=\theta^{N}_{t}+\beta_{\theta,t}G^{-1}_{t}\tilde{\delta}_{t}\cdot\psi_{t}.$
(28)

However, as given in Equation (9) these updates use the biased estimate of
$\nabla J(\cdot)$. Moreover, the Fisher information matrix inverse is updated
via the Sherman-Morrison iterative method. In this Section, we work with the
deterministic variants of these algorithms where we use $\nabla J(\cdot)$
instead of $\tilde{\delta}_{t}\cdot\psi_{t}$, and $G(\theta^{N}_{t})^{-1}$
instead of using $G_{t}^{{-1}}$ in the actor updates. This avoids the
approximation errors as in Equation (9); however, the same is not possible in
the computations since the gradient of the objective function is not known.
For ease of notation, we denote the actor parameters in the deterministic
variants of MAAC and FI-MAN algorithms by $\tilde{\theta}^{M}$, and
$\tilde{\theta}^{N}$, respectively. In particular, we consider the following
actor updates.

$\displaystyle\textbf{Deterministic MAAC:}~{}~{}\tilde{\theta}^{M}_{t+1}$
$\displaystyle=\tilde{\theta}^{M}_{t}+\beta_{\tilde{\theta},t}\nabla
J(\tilde{\theta}^{M}_{t});$ (29) $\displaystyle\textbf{Deterministic FI-
MAN:}~{}~{}\tilde{\theta}^{N}_{t+1}$
$\displaystyle=\tilde{\theta}^{N}_{t}+\beta_{\tilde{\theta},t}G(\tilde{\theta}^{N}_{t})^{-1}{\nabla}J(\tilde{\theta}^{N}_{t})$
$\displaystyle=\tilde{\theta}^{N}_{t}+\beta_{\tilde{\theta},t}\widetilde{\nabla}J(\tilde{\theta}^{N}_{t})$

We give sufficient conditions when the objective function value of the limit
point of the deterministic FI-MAN algorithm is not worse off than the value by
deterministic MAAC algorithm while using the above actor updates. We want to
emphasize that with these updates, the actor parameters in Equation (29) will
converge to a local maxima under some conditions (for example, the strong
Wolfe’s conditions) on the step-size [Nocedal and Wright, 2006]. Let
$\tilde{\theta}^{M^{\star}}$ and $\tilde{\theta}^{N^{\star}}$ be the
corresponding local maxima. The existence of the local maxima for the
deterministic MAN algorithms is also guaranteed via the Wolfe’s conditions in
the natural gradients space. Note that these local maxima need not be the same
as the one obtained from actor updates given in Equation (28). However, the
result given below may be valid for the MAAC and FI-MAN algorithms because
both $\tilde{\delta}\cdot\psi$ and $\nabla J(\cdot)$ go to zero
asymptotically.

We also assume that both algorithms use the same sequence of step-sizes,
$\\{\beta_{\tilde{\theta},t}\\}$. Moreover, proof of the results in this
section uses Taylor’s series expansion and comparison of the objective
function, $J(\cdot)$, rather than its estimate $\mu$. Similar ideas are used
in [Aoki, 2016, Patchell and Jacobs, 1971] where the certainty equivalence
principle holds, i.e., the random variables are replaced by their expected
values. However, we work with the estimates in convergence theory/proofs and
computations since the value of the global objective is unknown to the agents.

First, we need to bound the minimum singular value of the Fisher information
matrix as in the following Lemma.

######  Lemma 2.

For the Fisher information matrix, $G(\theta)=\mathbb{E}[\psi\psi^{\top}]$,
such that $||\psi||\leq 1$, the minimum singular value,
$\sigma_{\min}(G(\theta))$ is upper bounded by $\frac{1}{m}$,

$\sigma_{\min}(G(\theta))\leq\frac{1}{m}.$ (30)

The proof of this Lemma is based on the observation that the trace of matrix
$\psi\psi^{\top}$ is $||\psi||^{2}$. We include the proof in Appendix A.3.

######  Remark 4.

In literature, the compatible features are assumed to be uniformly bounded,
Assumption X. 3. For the linear architecture of features that we are using,
assuming this bound to be 1 is not restrictive. The features $\psi$, that we
use in our computational experiments in Section 5, automatically meet the
condition of being normalized by 1, i.e., $||\psi||\leq 1$.

######  Lemma 3.

Let $J(\cdot)$ be twice continuously differentiable function on a compact set
$\Theta$, so that $|\\{\nabla^{2}J(\tilde{\theta}^{M}_{t})\\}_{(i,j)}|\leq
H,~{}\forall~{}i,j\in[m]$ for some $H<\infty$. Moreover, let
$J(\tilde{\theta}^{M}_{t})\leq J(\tilde{\theta}^{N}_{t})$, $||\nabla
J(\tilde{\theta}^{M}_{t})||\leq||\nabla J(\tilde{\theta}^{N}_{t})||$, and
$\beta_{\tilde{\theta},{t}}\frac{mH}{2}+{1}-m^{2}\leq 0$. Then,
$J(\tilde{\theta}^{M}_{t+1})\leq J(\tilde{\theta}^{N}_{t+1})$.

###### Proof.

The Taylor series expansion of a twice differentiable function
$J(\tilde{\theta}^{M}_{t+1})$ with Lagrange form of remainder [Folland, 1999]
is

$J(\tilde{\theta}^{M}_{t+1})=J(\tilde{\theta}^{M}_{t}+\Delta\tilde{\theta}^{M}_{t})=J(\tilde{\theta}^{M}_{t})+\Delta\tilde{\theta}_{t}^{M^{\top}}\nabla
J(\tilde{\theta}^{M}_{t})+R_{M}(\Delta\tilde{\theta}^{M}_{t}),~{}where$ (31)

$R_{M}(\Delta\tilde{\theta}^{M}_{t})=\frac{1}{2!}\Delta\tilde{\theta}_{t}^{M^{\top}}\nabla^{2}J(\tilde{\theta}^{M}_{t}+c_{M}\cdot\Delta\tilde{\theta}^{M}_{t})\Delta\tilde{\theta}^{M}_{t}$
for some $c_{M}\in(0,1)$.

Similarly, the Taylor series expansion of $J(\tilde{\theta}^{N}_{t+1})$ with
Lagrange form of remainder is

$J(\tilde{\theta}^{N}_{t+1})=J(\tilde{\theta}^{N}_{t}+\Delta\tilde{\theta}^{N}_{t})=J(\tilde{\theta}^{N}_{t})+\Delta\tilde{\theta}_{t}^{N^{\top}}\widetilde{\nabla}J(\tilde{\theta}^{N}_{t})+R_{N}(\Delta\tilde{\theta}^{N}_{t}),~{}where$
(32)

$R_{N}(\Delta\tilde{\theta}^{N}_{t})=\frac{1}{2!}\Delta\tilde{\theta}_{t}^{N^{\top}}\widetilde{\nabla}^{2}J(\tilde{\theta}^{N}_{t}+c_{N}\cdot\Delta\tilde{\theta}^{N}_{t})\Delta\tilde{\theta}^{N}_{t}$
for some $c_{N}\in(0,1)$.

Now, consider the difference
$J(\tilde{\theta}^{M}_{t+1})-J(\tilde{\theta}^{N}_{t+1})$,

$\displaystyle=$ $\displaystyle
J(\tilde{\theta}^{M}_{t})-J(\tilde{\theta}^{N}_{t})+\Delta\tilde{\theta}^{M^{\top}}_{t}\nabla
J(\tilde{\theta}^{M}_{t})-\Delta\tilde{\theta}^{N^{\top}}_{t}\widetilde{\nabla}J(\tilde{\theta}^{N}_{t})+R_{M}(\Delta\tilde{\theta}^{M}_{t})-R_{N}(\Delta\tilde{\theta}^{N}_{t})$
(33) $\displaystyle\overset{(i)}{\leq}$
$\displaystyle\Delta\tilde{\theta}^{M^{\top}}_{t}\nabla
J(\tilde{\theta}^{M}_{t})-\Delta\tilde{\theta}^{N^{\top}}_{t}G(\tilde{\theta}^{N}_{t})^{-1}\nabla
J(\tilde{\theta}^{N}_{t})+R_{M}(\Delta\tilde{\theta}^{M}_{t})$
$\displaystyle\overset{(ii)}{=}$
$\displaystyle(\tilde{\theta}^{M}_{t+1}-\tilde{\theta}^{M}_{t})^{\top}J(\tilde{\theta}^{M}_{t})-(\tilde{\theta}^{N}_{t+1}-\tilde{\theta}^{N}_{t})^{\top}G(\tilde{\theta}^{N}_{t})^{-1}\nabla
J(\tilde{\theta}^{N}_{t})+R_{M}(\Delta\tilde{\theta}^{M}_{t})$
$\displaystyle\overset{(iii)}{=}$
$\displaystyle\beta_{\tilde{\theta},{t}}\left(||\nabla
J(\tilde{\theta}^{M}_{t})||^{2}-||G(\tilde{\theta}^{N}_{t})^{-1}\nabla
J(\tilde{\theta}^{N}_{t}))||^{2}\right)+R_{M}(\Delta\tilde{\theta}^{M}_{t})$
$\displaystyle\overset{(iv)}{\leq}$
$\displaystyle\beta_{\tilde{\theta},{t}}\left(||\nabla
J(\tilde{\theta}^{N}_{t})||^{2}-||G(\tilde{\theta}^{N}_{t})^{-1}\nabla
J(\tilde{\theta}^{N}_{t}))||^{2}\right)+R_{M}(\Delta\tilde{\theta}^{M}_{t})$

where $(i)$ follows because $J(\tilde{\theta}^{M}_{t})\leq
J(\tilde{\theta}^{N}_{t})$, $R_{N}(\Delta\tilde{\theta}^{N}_{t})\geq 0$ and
$\widetilde{\nabla}J(\tilde{\theta}^{N}_{t})=G(\tilde{\theta}^{N}_{t})^{-1}\nabla
J(\tilde{\theta}^{N}_{t})$. $(ii)$ uses the fact that
$\Delta\tilde{\theta}^{M}_{t}=\tilde{\theta}^{M}_{t+1}-\tilde{\theta}^{M}_{t};~{}\Delta\tilde{\theta}^{N}_{t}=\tilde{\theta}^{N}_{t+1}-\tilde{\theta}^{N}_{t}$.
$(iii)$ is the consequence of updates in Equation (29). Finally, $(iv)$
follows from the fact that $||\nabla J(\tilde{\theta}^{M}_{t})||\leq||\nabla
J(\tilde{\theta}^{N}_{t})||$.

Now, from Equation (33) and using the fact that for any positive definite
matrix $\mathbf{A}$ and a vector $\mathbf{v}$,
$||\mathbf{A}\mathbf{v}||\geq\sigma_{\min}(\mathbf{A})||\mathbf{v}||$, we have

$\displaystyle||G(\tilde{\theta}^{N}_{t})^{-1}\nabla
J(\tilde{\theta}^{N}_{t}))||^{2}$ $\displaystyle\geq$
$\displaystyle\sigma_{\min}^{2}(G(\tilde{\theta}^{N}_{t})^{-1})||\nabla
J(\tilde{\theta}^{N}_{t}))||^{2},$
$\displaystyle\implies~{}-||G(\tilde{\theta}^{N}_{t})^{-1}\nabla
J(\tilde{\theta}^{N}_{t}))||^{2}$ $\displaystyle\leq$
$\displaystyle-\frac{1}{\sigma_{\min}^{2}(G(\tilde{\theta}^{N}_{t}))}||\nabla
J(\tilde{\theta}^{N}_{t}))||^{2}.$

Therefore, from Equation (33), we have

$\displaystyle J(\tilde{\theta}^{M}_{t+1})-J(\tilde{\theta}^{N}_{t+1})$
$\displaystyle\leq$
$\displaystyle\beta_{\tilde{\theta},t}\left(1-\frac{1}{\sigma_{\min}^{2}(G(\tilde{\theta}^{N}_{t}))}\right)||\nabla
J(\tilde{\theta}^{N}_{t}))||^{2}+R_{M}(\Delta\tilde{\theta}^{M}_{t})$ (34)
$\displaystyle\overset{(v)}{\leq}$
$\displaystyle\beta_{\tilde{\theta},{t}}\left(1-m^{2}\right)||\nabla
J(\tilde{\theta}^{N}_{t}))||^{2}+R_{M}(\Delta\tilde{\theta}^{M}_{t}),$

where $(v)$ follows from Lemma 2 as
$\sigma_{\min}(G(\tilde{\theta}^{N}_{t}))\leq\frac{1}{m}$, implies
$-\frac{1}{\sigma_{\min}^{2}(G(\tilde{\theta}^{N}_{t}))}\leq-m^{2}$.

Since $J(\cdot)$ is twice continuously differentiable function on the compact
set $\Theta$, we have for all $i,j\in[m]$,
$|\\{\nabla^{2}J(\tilde{\theta}^{M}_{t}\\}_{(i,j)}|\leq H<\infty$. In above
Taylor’s series expansion, we then have

$\displaystyle|R_{M}(\Delta\tilde{\theta}^{M}_{t})|\leq\frac{H}{2!}||\Delta\tilde{\theta}^{M}_{t}||^{2}_{1}$
$\displaystyle\overset{(vii)}{=}$
$\displaystyle\beta_{\tilde{\theta},{t}}^{2}\frac{H}{2}||\nabla
J(\tilde{\theta}^{M}_{t})||^{2}_{1}$ $\displaystyle\overset{(viii)}{\leq}$
$\displaystyle\beta_{\tilde{\theta},{t}}^{2}\frac{mH}{2}||\nabla
J(\tilde{\theta}^{M}_{t})||^{2}$ $\displaystyle\overset{(ix)}{\leq}$
$\displaystyle\beta_{\tilde{\theta},{t}}^{2}\frac{mH}{2}||\nabla
J(\tilde{\theta}^{N}_{t})||^{2},$

where $(vii)$ follows from actor update of the deterministic FI-MAN algorithm.
$(viii)$ holds because for any $\mathbf{x}\in\mathbb{R}^{l}$, the following is
true:
$||\mathbf{x}||_{2}\leq||\mathbf{x}||_{1}\leq\sqrt{l}~{}||\mathbf{x}||_{2}$
[Horn and Johnson, 2012]. $(ix)$ comes from the assumption that $||\nabla
J(\tilde{\theta}^{M}_{t})||^{2}\leq||\nabla J(\tilde{\theta}^{N}_{t})||^{2}$.
Now, from Equation (34) and above upper bound, we have

$\displaystyle J(\tilde{\theta}^{M}_{t+1})-J(\tilde{\theta}^{N}_{t+1})$
$\displaystyle\leq$
$\displaystyle\beta_{\tilde{\theta},{t}}\left(1-m^{2}\right)||\nabla
J(\tilde{\theta}^{N}_{t}))||^{2}+\beta_{\tilde{\theta},{t}}^{2}\frac{mH}{2}||\nabla
J(\tilde{\theta}^{N}_{t})||^{2}$ (35) $\displaystyle=$
$\displaystyle\beta_{\tilde{\theta},{t}}\left\\{\beta_{\tilde{\theta},{t}}\frac{mH}{2}+{1}-m^{2}\right\\}||\nabla
J(\tilde{\theta}^{N}_{t})||^{2}$ $\displaystyle\leq$ $\displaystyle 0,$

where the last inequality follows from the assumption
$\beta_{\tilde{\theta},{t}}\frac{mH}{2}+{1}-m^{2}\leq 0$. Therefore,
$J(\tilde{\theta}^{M}_{t+1})\leq J(\tilde{\theta}^{N}_{t+1})$.  ∎

######  Theorem 3.

Let $J(\cdot)$ be twice continuously differentiable function on a compact set
$\Theta$, so that $|\\{\nabla^{2}J(\tilde{\theta}^{M}_{t})\\}_{(i,j)}|\leq
H,~{}\forall~{}i,j\in[m]$ for some $H<\infty$. Moreover, let
$J(\tilde{\theta}^{M}_{t_{0}})\leq J(\tilde{\theta}^{N}_{t_{0}})$ for some
$t_{0}>0$, and for every $t\geq t_{0}$, let $||\nabla
J(\tilde{\theta}^{M}_{t})||\leq||\nabla J(\tilde{\theta}^{N}_{t})||$, and
$\beta_{\tilde{\theta},t}\frac{mH}{2}+1-m^{2}\leq 0$. Then,
$J(\tilde{\theta}^{M}_{t})\leq J(\tilde{\theta}^{N}_{t})$, for all $t\geq
t_{0}$.  Further for the local maxima $\tilde{\theta}^{M^{\star}}$, and
$\tilde{\theta}^{N^{\star}}$ of the updates in Equation (29) we have
$J(\tilde{\theta}^{M^{\star}})\leq J(\tilde{\theta}^{N^{\star}})$.

###### Proof.

We prove this theorem via Principle of Mathematical Induction (PMI). From
assumption, we have $J(\tilde{\theta}^{M}_{t_{0}})\leq
J(\tilde{\theta}^{N}_{t_{0}})$. Now, using $t=t_{0}$ in the Lemma 3, under the
assumptions, we have $J(\tilde{\theta}^{M}_{t_{0}+1})\leq
J(\tilde{\theta}^{N}_{t_{0}+1})$. Thus, the base case of PMI is true.

Next, we assume that $J(\tilde{\theta}^{M}_{t})\leq J(\tilde{\theta}^{N}_{t})$
for any $t=t_{0}+k$, where $k\in\mathbb{Z}^{+}$. Also, from assumption, for
every $t\geq t_{0}+k$, we have $||\nabla
J(\tilde{\theta}^{M}_{t})||\leq||\nabla J(\tilde{\theta}^{N}_{t})||$, and
$\beta_{\tilde{\theta},t}\frac{mH}{2}+1-m^{2}\leq 0$. Therefore, again from
Lemma 3 we have $J(\tilde{\theta}^{M}_{t_{0}+k+1})\leq
J(\tilde{\theta}^{N}_{t_{0}+k+1})$. From PMI we have

$J(\tilde{\theta}^{M}_{t})\leq
J(\tilde{\theta}^{N}_{t}),~{}~{}\forall~{}~{}t\geq t_{0}.$

Next, consider the limiting case. Taking the limit $t\rightarrow\infty$ in the
above equation and using the fact that $J(\cdot)$ is continuous on the compact
set $\Theta$, we have

$lim_{t\rightarrow\infty}J(\tilde{\theta}^{M}_{t})=J(\tilde{\theta}^{M^{\star}}),~{}and~{}lim_{t\rightarrow\infty}J(\tilde{\theta}^{N}_{t})=J(\tilde{\theta}^{N^{\star}}).$
(36)

This ends the proof. ∎

The following subsection will highlight some consequences of using the
Boltzmann policy.

###  3.6 KL divergence based natural gradients for Boltzmann policy

One specific policy that is often used in RL literature is the Boltzmann
policy [Doan et al., 2021]. Recall, the parameterized Boltzmann policy is
given as

$\pi_{\theta_{t}}(s,a)=\frac{\exp(q^{\top}_{s,a}\theta_{t})}{\sum_{b\in\mathcal{A}}\exp(q^{\top}_{s,b}\theta_{t})},$
(37)

where $q^{\top}_{s,a}$ is the feature for any $(s,a)$. Here the features
$q_{s,a}$ are assumed to be uniformly bounded by 1.

######  Lemma 4.

For the Boltzmann policy as given in Equation (37) the KL divergence between
policy parameterized by $\theta_{t}$ and $\theta_{t}+\Delta\theta_{t}$ is
given by

$KL(\pi_{\theta_{t}}(s,a)||\pi_{\theta_{t}+\Delta\theta_{t}}(s,a))=\mathbb{E}\left[\log\left(\sum_{b\in\mathcal{A}}\pi_{\theta_{t}}(s,b)\exp(\Delta
q^{\top}_{s,ba}\Delta\theta_{t})\right)\right],$ (38)

where $\Delta q^{\top}_{s,ba}=q^{\top}_{s,b}-q^{\top}_{s,a}$.

The proof of this lemma is deferred to Appendix A.4. The above KL divergence
represents that we have a non-zero curvature if the action taken is better
than the averaged action. From above equation we also observe that
$\exp(\Delta q_{s,ba}\Delta\theta_{t})\neq 1$ if and only if ${\Delta
q_{s,ba}}$ is orthogonal to $\Delta\theta_{t}$. So, except when they are
orthogonal, $\log(\sum_{b\in\mathcal{A}}\pi_{\theta_{t}}(s,b)\cdot\exp{(\Delta
q_{s,ba}\Delta\theta_{t}}))\neq 0$ as
$\sum_{b\in\mathcal{A}}\pi_{\theta_{t}}(s,b)=1$. Thus, the curvature is non-
zero, larger or smaller depends on the direction $\Delta\theta_{t}$ makes with
that of feature difference $q_{s,b}^{\top}-q^{\top}_{s,a}$; if the angle is
zero, it is better.

Next lemma provide the derivative of KL divergence between policy
$\pi_{\theta_{t}}$, and $\pi_{\theta_{t}+\Delta\theta_{t}}$.

######  Lemma 5.

For the Boltzmann policy as given in Equation (37) we have

$\nabla
KL(\pi_{\theta_{t}}(\cdot,\cdot)||\pi_{\theta_{t}+\Delta\theta_{t}}(\cdot,\cdot))=-\mathbb{E}[\nabla\log\pi_{\theta_{t}+\Delta\theta_{t}}(s,a)],$
(39)

i.e., $\psi_{\theta_{t+1}}=\nabla\log\pi_{\theta_{t}+\Delta\theta_{t}}$ is an
unbiased estimate of $\nabla
KL(\pi_{\theta_{t}}(\cdot,\cdot)||\pi_{\theta_{t}+\Delta\theta_{t}}(\cdot,\cdot))$.
Proof of this lemma is available in Appendix A.5. The proof uses the fact that
for Boltzmann policies the compatible features are same as the features
associated to policy, except normalized to be mean zero for each state [Sutton
et al., 1999].

Recall, in Equation (13) we provide the approximate derivative of KL
divergence using second order Taylor approximation of the objective function
as

$\nabla
KL(\pi_{\theta_{t}}(\cdot,\cdot)||\pi_{\theta_{t}+\Delta\theta_{t}}(\cdot,\cdot))\approx
G(\theta_{t})\Delta\theta_{t}.$ (40)

Moreover, from Equation (15) we have
$G(\theta_{t})\Delta\theta_{t}=-\frac{1}{\rho_{t}}\nabla_{\theta}J(\theta_{t})$.
Also, from Lemma 1 we have,

$\nabla
KL(\pi_{\theta_{t}}(\cdot,\cdot)||\pi_{\theta_{t}+\Delta\theta_{t}}(\cdot,\cdot))\approx-\frac{1}{\rho_{t}}\nabla
J(\theta_{t}).$

Thus, combining Lemma 5, and Equation (40) for Boltzmann policies we have

$\mathbb{E}[\nabla\log\pi_{\theta_{t}+\Delta\theta_{t}}(s,a)]\approx\frac{1}{\rho_{t}}\nabla
J(\theta_{t}),$ (41)

i.e., $\nabla\log\pi_{\theta_{t}+\Delta\theta_{t}}=\psi_{\theta_{t+1}}$ is
approximately an unbiased estimate of $\nabla J(\theta_{t})$ upto scaling of
$\frac{1}{\rho_{t}}$ for the Boltzmann policies. It is a valuable observation
because to move along the gradient of objective function $J(\cdot)$, we can
adjust the updates (of actor parameter) just by moving in the
$\pi_{\theta_{t}}$ prediction space via the compatible features.

We now prove the convergence of FI-MAN, AP-MAN, and FIAP-MAN algorithms. The
proofs majorly use the idea of two-time scale stochastic approximations from
[Borkar, 2009].

##  4 Convergence analysis

This section provides the convergence proof of all the 3 MAN algorithms. To
this end, we need following assumptions on the features $\varphi(s)$ of the
value function, and $f(s,a)$ of the rewards for any
$s\in\mathcal{S},a\in\mathcal{A}$. This assumption is similar to [Zhang et
al., 2018], and also used in the convergence proof for single-agent natural
actor-critic [Bhatnagar et al., 2009a].

######  X. 3.

The feature vectors $\varphi(s)$, and $f(s,a)$ associated with the value
function and the reward function are uniformly bounded for any
$s\in\mathcal{S},a\in\mathcal{A}$. Moreover, let the feature matrix
$\varPhi\in\mathbb{R}^{|\mathcal{S}|\times L}$ have
$[\varphi_{l}(s),s\in\mathcal{S}]^{\top}$ as its $l$-th column for any
$l\in[L]$, and feature matrix
$F\in\mathbb{R}^{|\mathcal{S}||\mathcal{A}|\times M}$ have
$[f_{m}(s,a),s\in\mathcal{S},a\in\mathcal{A}]^{\top}$ as its $m$-th column for
any $m\in[M]$, then $\varPhi$ and $F$ have full column rank, and for any
$\omega\in\mathbb{R}^{L}$, we have $\varPhi\omega\neq\mathbbm{1}$.

Apart from assumption X. 3, let
$D^{s}_{\theta}=[d_{\theta}(s),s\in\mathcal{S}]$, and
$\bar{R}_{\theta}=[\bar{R}_{\theta}(s),s\in\mathcal{S}]^{\top}\in\mathbb{R}^{|\mathcal{S}|}$
with $\bar{R}_{\theta}(s)=\sum_{a}\pi_{\theta}(s,a)\cdot\bar{R}(s,a)$. Define
the operator
$T^{V}_{\theta}:\mathbb{R}^{|\mathcal{S}|}\rightarrow\mathbb{R}^{|\mathcal{S}|}$
for any state value vector $X\in\mathbb{R}^{|\mathcal{S}|}$ as,

$T^{V}_{\theta}(X)=\bar{R}_{\theta}-J(\theta)\mathbbm{1}+P^{\theta}X.$

The proof of all the 3 MAN algorithms are done in two steps: (a) convergence
of the objective function estimate, critic update, and rewad parameters
keeping the actor parameters $\theta^{i}$ fixed for all agents $i\in N$, and
(b) convergence of the actor parameters to an asymptotically stable
equilibrium set of the ODE corresponding to the actor update. To this end, we
require the following assumption on Fisher information matrix $G^{i}_{t}$ and
its inverse $G^{i^{-1}}_{t}$. This assumption is used by [Bhatnagar et al.,
2009a] in case of single-agent natural actor-critic algorithms, here we have
suitably modified it for multi-agent setup.

######  X. 4.

For each agent $i\in N$, the recursions of Fisher information matrix
$G^{i}_{t}$, and its inverse $G^{i^{-1}}_{t}$ as given in Equations (18) and
(19) respectively satisfy
$sup_{t,\theta^{i},s,a^{i}}||G_{t}^{i}||<\infty;~{}~{}sup_{t,\theta^{i},s,a^{i}}||G_{t}^{i^{-1}}||<\infty.$

Assumption X. 4 ensures that the FI-MAN and FIAP-MAN actor-critic algorithms
does not get stuck in a non-stationary point. A sufficient condition for both
requirements of assumption X. 4 is following: for each agent $i\in N$, for
some scalars $c^{i}_{1},c^{i}_{2}>0$,

$c^{i}_{1}||x^{i}||^{2}\leq
x^{i^{\top}}\psi^{i}_{s,a^{i}}\psi^{i^{\top}}_{s,a^{i}}x^{i}\leq
c^{i}_{2}||x^{i}||^{2},~{}~{}\forall~{}s\in\mathcal{S},a^{i}\in\mathcal{A}^{i},x^{i},\theta^{i}\in\mathbb{R}^{m_{i}}.$

Therefore, for each agent $i\in N$, we have $\bar{c}^{i}_{1}||x^{i}||^{2}\leq
x^{i^{\top}}G^{i}x^{i}\leq\bar{c}^{i}_{2}||x^{i}||^{2}$, and the eigenvalues
of $G^{i}$ lie between some positive scalars $\bar{c}^{i}_{1}$, and
$\bar{c}^{i}_{2}$. Since,
$\bar{c}^{i}_{1},\bar{c}^{i}_{2}>0,~{}~{}\forall~{}i\in N$, thus from
Propositions A.9 and A.15 of [Bertsekas, 1997] the algorithms will not get
stuck at non-stationary points. Moreover using stochastic approximation
technique we know that $G^{i}_{t}$ will converge asymptotically to
$G(\theta^{i})$ almost surely if $\theta^{i}$ is held fixed [Borkar, 2009].

To ensure the existence of local optima of $J(\theta)$ we make the following
assumptions on policy parameters, $\theta^{i}_{t}$ for each agent $i\in N$.

######  X. 5.

The policy parameters $\\{\theta^{i}_{t}\\}_{t\geq 0}$ update includes a
projection operator
$\Gamma^{i}:\mathbb{R}^{m_{i}}\rightarrow\Theta^{i}\subset\mathbb{R}^{m_{i}}$,
that projects, for every $t\geq 0$, $\theta^{i}_{t}$ onto a compact set
$\Theta^{i}$. Moreover, $\Theta=\prod_{i=1}^{n}\Theta^{i}$ is large enough to
include at least one local optima of $J(\theta)$.

For each agent $i\in N$, let $\hat{\Gamma}^{i}$ be the transformed projection
operator defined for any $\theta\in\Theta$ with
$h:\Theta\rightarrow\mathbb{R}^{\sum_{i\in N}m_{i}}$ being a continuous
function as follows:

$\hat{\Gamma}^{i}(h(\theta))=lim_{0<\eta\rightarrow
0}\frac{\Gamma^{i}(\theta^{i}+\eta h(\theta))-\theta^{i}}{\eta}.$ (42)

If the above limit is not unique, $\hat{\Gamma}^{i}(h(\theta))$ denotes the
set of all possible limit points of Equation (42). The above projection
operator is useful in convergence proof of the policy parameters. It is an
often-used technique to ensure boundedness of iterates in stochastic
approximation algorithms. However, we do not require a projection operator in
computations because iterates remain bounded.

We begin by proving the convergence of the updates given in Equations (5),
(6), and (7), respectively. The following theorem will be common in the proof
of all the 3 MAN algorithms.

######  Theorem 4.

Under assumptions X. 1, X. 2, and X. 3, for any policy $\pi_{\theta}$, with
sequences $\\{\lambda^{i}_{t}\\},\\{\mu^{i}_{t}\\},\\{v^{i}_{t}\\}$, we have
$lim_{t}~{}\mu^{i}_{t}=J(\theta),~{}lim_{t}~{}\lambda^{i}_{t}=\lambda_{\theta}$,
and $lim_{t}~{}v^{i}_{t}=v_{\theta}$ a.s. for each agent $i\in N$, where
$J(\theta),~{}\lambda_{\theta}$, and $v_{\theta}$ are unique solutions to

$\displaystyle F^{\top}D_{\theta}^{s,a}(\bar{R}-F\lambda_{\theta})$
$\displaystyle=$ $\displaystyle 0,$
$\displaystyle\varPhi^{\top}D_{\theta}^{s}[T_{\theta}^{V}(\varPhi
v_{\theta})-\varPhi v_{\theta}]$ $\displaystyle=$ $\displaystyle 0.$

Proof of this theorem follows from [Zhang et al., 2018]. For the sake of
completeness, we briefly present the proof in Appendix A.6.

###  4.1 Convergence of FI-MAN actor-critic algorithm

To prove the convergence of FI-MAN algorithm we first show the convergence of
recursion for the Fisher information matrix inverse as in Equation (19).

######  Theorem 5.

For each agent $i\in N$, and given parameter $\theta^{i}$, we have
$G_{t}^{i^{-1}}\rightarrow G(\theta^{i})^{-1}$ as $t\rightarrow\infty$ with
probability one.

###### Proof.

Consider the following difference for each agent $i\in N$,

$\displaystyle||G^{i^{-1}}_{t}-G(\theta^{i})^{-1}||$ $\displaystyle=$
$\displaystyle||G(\theta^{i})^{-1}G(\theta^{i})G^{i^{-1}}_{t}-G(\theta^{i})^{-1}G^{i}_{t}G^{i^{-1}}_{t}||$
$\displaystyle=$
$\displaystyle||G(\theta^{i})^{-1}(G(\theta^{i})-G^{i}_{t})G^{i^{-1}}_{t}||$
$\displaystyle\leq$ $\displaystyle
sup_{\theta^{i}}||G(\theta^{i})^{-1}||~{}sup_{t,s,a^{i}}||G^{i^{-1}}_{t}||~{}||G(\theta^{i})-G_{t}^{i}||$
$\displaystyle\rightarrow$ $\displaystyle 0~{}as~{}t\rightarrow\infty.$

The above inequality follows from the induced matrix norm property and
assumption X. 4. ∎

Next, we prove the convergence of actor update. To this end, we view
$-r^{i}_{t+1}$ as the cost incurred at time $t$. Hence, transform the actor
recursion in the FI-MAN algorithm as

$\theta^{i}_{t+1}\leftarrow\theta^{i}_{t}-\beta_{\theta,t}\cdot
G_{t}^{i^{-1}}\cdot\tilde{\delta}^{i}_{t}\cdot\psi^{i}_{t}.$

The convergence of the FI-MAN actor-critic algorithm with linear function
approximation is given in the following theorem.

######  Theorem 6.

Under the assumptions X. 1 \- X. 5, the sequence $\\{\theta^{i}_{t}\\}_{t\geq
0}$ obtained from the actor step of the FI-MAN algorithm converges almost
surely to asymptotically stable equilibrium set of the ODE

$\dot{\theta}^{i}=\hat{\Gamma}^{i}[-G(\theta^{i})^{-1}\mathbb{E}_{s_{t}\sim
d_{\theta},a_{t}\sim\pi_{\theta}}(\tilde{\delta}^{i}_{t,\theta}\psi^{i}_{t,\theta})],~{}~{}~{}\forall~{}i\in
N.$ (43)

###### Proof.

Let $\mathcal{F}_{t,1}=\sigma(\theta_{\tau},\tau\leq t)$ be the $\sigma$-field
generated by $\\{\theta_{\tau}\\}_{\tau\leq t}$. Let

$\displaystyle\xi_{t+1,1}^{i}$ $\displaystyle=$
$\displaystyle-G(\theta^{i}_{t})^{-1}\left\\{\tilde{\delta}^{i}_{t}\psi^{i}_{t}-\mathbb{E}_{s_{t}\sim
d_{\theta_{t}},a_{t}\sim\pi_{\theta_{t}}}(\tilde{\delta}^{i}_{t}\psi^{i}_{t}|\mathcal{F}_{t,1})\right\\}$
$\displaystyle\xi_{t+1,2}^{i}$ $\displaystyle=$
$\displaystyle-G(\theta^{i}_{t})^{-1}\mathbb{E}_{s_{t}\sim
d_{\theta_{t}},a_{t}\sim\pi_{\theta_{t}}}((\tilde{\delta}^{i}_{t}-\tilde{\delta}^{i}_{t,\theta_{t}})\psi^{i}_{t}|\mathcal{F}_{t,1})$

where $\tilde{\delta}^{i}_{t,\theta_{t}}$ is defined as

$\tilde{\delta}^{i}_{t,\theta_{t}}=f_{t}^{\top}\lambda_{\theta_{t}}-J(\theta_{t})+\varphi_{t+1}^{\top}v_{\theta_{t}}-\varphi_{t}^{\top}v_{\theta_{t}}.$
(44)

The actor update in the FI-MAN algorithm with local projection then becomes,

$\theta^{i}_{t+1}=\Gamma^{i}[\theta^{i}_{t}-\beta_{\theta,t}G(\theta^{i}_{t})^{-1}\mathbb{E}_{s_{t}\sim
d_{\theta_{t}},a_{t}\sim\pi_{\theta_{t}}}(\tilde{\delta}^{i}_{t}\psi^{i}_{t}|\mathcal{F}_{t,1})+\beta_{\theta,t}\xi^{i}_{t+1,1}+\beta_{\theta,t}\xi^{i}_{t+1,2}].$
(45)

For a.s. convergence to the set of asymptotically stable equilibria of the ODE
Equation (43) for each $i\in N$, we appeal to Kushner-Clark lemma (see
appendix C.3). Below we verify the 3 main conditions of it.

First, note that $\xi_{t+1,2}=o(1)$ since critic converges at the faster time
scale, i.e.,
$\tilde{\delta}^{i}_{t}\rightarrow\tilde{\delta}^{i}_{t,\theta_{t}}$ a.s.
Next, let
$M^{1,i}_{t}=\sum_{\tau=0}^{t}\beta_{\theta,\tau}\xi^{i}_{\tau+1,1}$; then
$\\{M^{1,i}_{t}\\}$ is a martingale sequence. The sequences
$\\{z^{i}_{t}\\},\\{\psi^{i}_{t}\\},\\{G^{i^{-1}}_{t}\\}$, and
$\\{\varphi^{i}_{t}\\}$ are all bounded (by assumptions), and so is the
sequence $\\{\xi_{t,1}^{i}\\}$ (Here
$z^{i}_{t}=[\mu^{i}_{t},(\lambda^{i}_{t})^{\top},(v^{i}_{t})^{\top}]^{\top}$
is the same vector used in the proof of Theorem 4). Hence, we have
$\sum_{t}\mathbb{E}[||M^{1,i}_{t+1}-M^{1,i}_{t}||^{2}~{}|~{}\mathcal{F}_{t,1}]<\infty$
a.s., and hence the martingale sequence $\\{M^{1,i}_{t}\\}$ converges a.s.
[Neveu, 1975]. So, for any $\epsilon>0$, we have
$\underset{t\rightarrow\infty}{lim}~{}\mathbb{P}[sup_{p\geq
t}||\sum_{\tau=t}^{p}\beta_{\theta,\tau}\xi^{i}_{\tau,1}||\geq\epsilon]=0$, as
needed.

Regarding continuity of
$g^{1,i}(\theta_{t})=-G(\theta^{i}_{t})^{-1}\mathbb{E}_{s_{t}\sim
d_{\theta_{t}},a_{t}\sim\pi_{\theta_{t}}}(\tilde{\delta}^{i}_{t}\psi^{i}_{t}|\mathcal{F}_{t,1})$
we note that,

$\displaystyle g^{1,i}(\theta_{t})$ $\displaystyle=$
$\displaystyle-G(\theta^{i}_{t})^{-1}\mathbb{E}_{s_{t}\sim
d_{\theta_{t}},a_{t}\sim\pi_{\theta_{t}}}(\tilde{\delta}^{i}_{t}\psi^{i}_{t}|\mathcal{F}_{t,1})$
$\displaystyle=$
$\displaystyle-G(\theta^{i}_{t})^{-1}\sum_{s_{t}\in\mathcal{S},a_{t}\in\mathcal{A}}d_{\theta_{t}}(s_{t})\cdot\pi_{\theta_{t}}(s_{t},a_{t})\cdot\tilde{\delta}^{i}_{t,\theta_{t}}\cdot\psi^{i}_{t,\theta_{t}}.$

Firstly, $\psi^{i}_{t,\theta_{t}}$ is continuous by assumption X. 1. The term
$d_{\theta_{t}}(s_{t})\cdot\pi_{\theta_{t}}(s_{t},a_{t})$ is continuous in
$\theta^{i}_{t}$ since it is the stationary distribution and solution to
$d_{\theta_{t}}(s)\cdot\pi_{\theta_{t}}(s,a)=\sum_{s^{\prime}\in\mathcal{S},a^{\prime}\in\mathcal{A}}P^{\theta_{t}}(s^{\prime},a^{\prime}|s,a)\cdot
d_{\theta_{t}}(s^{\prime})\cdot\pi_{\theta_{t}}(s^{\prime},a^{\prime})$ and
$\sum_{s\in\mathcal{S},a\in\mathcal{A}}d_{\theta_{t}}(s)\cdot\pi_{\theta_{t}}(s,a)=1$,
where
$P^{\theta_{t}}(s^{\prime},a^{\prime}|s,a)=P(s^{\prime}|s,a)\cdot\pi_{\theta_{t}}(s^{\prime},a^{\prime})$.
From assumption X. 1, $\pi_{\theta_{t}}(s,a)>0$ and hence the above set of
linear equations has a unique solution that is continuous in $\theta_{t}$ by
assumption X. 1. Moreover, $\tilde{\delta}^{i}_{t,\theta_{t}}$ in Equation
(44) is continuous in $\theta^{i}_{t}$ since $v_{\theta_{t}}$ as the unique
solution to the linear equation
$\varPhi^{\top}D_{\theta}^{s}[T_{\theta}^{V}(\varPhi v_{\theta})-\varPhi
v_{\theta}]=0$ is continuous in $\theta_{t}$. Thus, $g^{1,i}(\theta_{t})$ is
continuous in $\theta^{i}_{t}$, as needed in Kushner-Clark lemma.

∎

Next, we provide the convergence of the AP-MAN algorithm. Recall, AP-MAN
algorithm does not use the Fisher information inverse estimate; instead, it
uses the linear function approximation of the advantage parameters.

###  4.2 Convergence of AP-MAN actor-critic algorithm

The convergence of critic step, the reward parameters and the objective
function estimate are the same as in Theorem 4. So, we show the convergence of
advantage parameters and actor updates as given in the AP-MAN algorithm.
Similar to the FI-MAN algorithm we again consider the transformed problem;
rewards replaced with costs. Thus the transformed recursion can be written as

${w}^{i}_{t+1}\leftarrow(I-\beta_{v,t}\psi^{i}_{t}\psi^{i^{\top}}_{t})w^{i}_{t}-\beta_{v,t}\tilde{\delta}^{i}_{t}\psi^{i}_{t}.$
(46)

######  Theorem 7.

Under the assumptions X. 3 and X. 4, for each agent $i\in N$, with actor
parameters $\theta^{i}$, we have
$w_{t}^{i}\rightarrow-G(\theta^{i})^{-1}\mathbb{E}[\tilde{\delta}^{i}_{t,\theta}\psi^{i}_{t}]$
as $t\rightarrow\infty$ with probability one.

###### Proof.

For each $i\in N$, the ODE associated with the recursion in Equation (46) for
a given $\theta$ is

$\dot{w}^{i}=\mathbb{E}_{s_{t}\sim
d_{\theta},a_{t}\sim\pi_{\theta}}[-\psi^{i}_{t}\psi^{i^{\top}}_{t}w^{i}-\tilde{\delta}^{i}_{t,\theta}\psi^{i}_{t}]=:g^{2,i}(w^{i})$
(47)

Note that $g^{2,i}(w^{i})$ is Lipschitz continuous in $w^{i}$. Let
$g^{2,i}_{\infty}(w^{i})=lim_{r\rightarrow\infty}\frac{g^{2,i}(rw^{i})}{r}$.
Note that $g^{2,i}_{\infty}(w^{i})$ exists and satisfies
$g^{2,i}_{\infty}(w^{i})=-G(\theta^{i})w^{i}$. For the ODE
$\dot{w}^{i}=-G(\theta^{i})w^{i}$ the origin is an asymptotically stable
equilibrium with $V_{1}(w^{i})=w^{i^{\top}}w^{i}/2$ as the associated Lyapunov
function (since $G(\theta^{i})$ is positive definite). Now define a sequence
$\\{M^{2,i}_{t}\\}$ as
$M^{2,i}_{t}=\hat{g}^{2,i}(w^{i}_{t})-\mathbb{E}[\hat{g}^{2,i}(w^{i}_{t})|\mathcal{F}_{t,2}]$,
where
$\hat{g}^{2,i}(w^{i}_{t})=-\psi^{i}_{t}\psi^{i^{\top}}_{t}w^{i}-\tilde{\delta}^{i}_{t}\psi^{i}_{t}$
and $\mathcal{F}_{t,2}=\sigma(w^{i}_{r},M^{2,i}_{r},r\leq t)$. Note that
$\\{M^{2,i}_{t}\\}$ is the martingale difference sequence. Thus there exists a
constant $C_{0}<\infty$ such that

$\mathbb{E}[||M^{2,i}_{t+1}||^{2}~{}|~{}\mathcal{F}_{t,2}]\leq
C_{0}(1+||w^{i}_{t}||^{2}),~{}~{}\forall~{}t\geq 0.$

For the ODE given in Equation (47) consider the function $V_{2}(w^{i})$
defined by

$V_{2}(w^{i})=\frac{1}{2}(w^{i}+G(\theta^{i})^{-1}\mathbb{E}[\tilde{\delta}^{i}_{t,\theta}\psi^{i}_{t}])^{\top}(w^{i}+G(\theta^{i})^{-1}\mathbb{E}[\tilde{\delta}^{i}_{t,\theta}\psi^{i}_{t}]).$

Since $G(\theta^{i})^{-1}$ is a positive definite matrix, we have

$\displaystyle\frac{dV_{2}(w^{i})}{dt}$ $\displaystyle=$ $\displaystyle\nabla
V_{2}(w^{i})^{\top}\dot{w}^{i}$ $\displaystyle=$
$\displaystyle-(w^{i}+G(\theta^{i})^{-1}\mathbb{E}[\tilde{\delta}^{i}_{t,\theta}\psi^{i}_{t}])^{\top}(G(\theta^{i})w^{i}+\mathbb{E}[\tilde{\delta}^{i}_{t,\theta}\psi^{i}_{t}])$
$\displaystyle=$
$\displaystyle-(w^{i}+G(\theta^{i})^{-1}\mathbb{E}[\tilde{\delta}^{i}_{t,\theta}\psi^{i}_{t}])^{\top}~{}G(\theta^{i})~{}(w^{i}+G(\theta^{i})^{-1}\mathbb{E}[\tilde{\delta}^{i}_{t,\theta}\psi^{i}_{t}])$
$\displaystyle<$ $\displaystyle
0,~{}~{}\forall~{}w^{i}\neq-G(\theta^{i})^{-1}\mathbb{E}[\tilde{\delta}^{i}_{t,\theta}\psi^{i}_{t}].$

Thus,
$w(\theta^{i})=-G(\theta^{i})^{-1}\mathbb{E}[\tilde{\delta}^{i}_{t,\theta}\psi^{i}_{t}]$
is an asymptotically stable equilibrium solution for the ODE given in Equation
(47). Now, from the Theorem 2.2 of [Borkar and Meyn, 2000] recursion (46)
converges to $w(\theta^{i})$ with probability one. This concludes the proof.

∎

We now consider the convergence of actor update of the AP-MAN algorithm.

######  Theorem 8.

Under the assumptions X. 1 \- X. 5, the sequence $\\{\theta^{i}_{t}\\}$
obtained from the actor step of the AP-MAN algorithm converges a.s. to
asymptotically stable equilibrium set of

$\dot{\theta}^{i}=\hat{\Gamma}^{i}[-G(\theta^{i})^{-1}\mathbb{E}_{s_{t}\sim
d_{\theta},a_{t}\sim\pi_{\theta}}(\tilde{\delta}^{i}_{t,\theta}\psi^{i}_{t,\theta})],~{}~{}~{}\forall~{}i\in
N.$ (48)

###### Proof.

The proof is similar to that of Theorem 6. So, we avoid writing many details
here. Let $\mathcal{F}_{t,3}=\sigma(\theta_{\tau},\tau\leq t)$ be the sigma
field generated by $\\{\theta_{\tau}\\}_{\tau\leq t}$. The actor update in the
AP-MAN algorithm with local projection is

$\theta^{i}_{t+1}=\Gamma^{i}[\theta^{i}_{t}-\beta_{\theta,t}\mathbb{E}_{s_{t}\sim
d_{\theta_{t}},a_{t}\sim\pi_{\theta_{t}}}(G(\theta^{i}_{t})^{-1}\tilde{\delta}^{i}_{t}\psi^{i}_{t}|\theta^{i}_{t})+\beta_{\theta,t}\xi_{t+1,3}^{i}],$
(49)

where $\xi_{t+1,3}^{i}=G(\theta^{i}_{t})^{-1}\mathbb{E}_{s_{t}\sim
d_{\theta_{t}},a_{t}\sim\pi_{\theta_{t}}}((\tilde{\delta}^{i}_{t}-\tilde{\delta}^{i}_{t,\theta_{t}})\cdot\psi^{i}_{t,\theta}~{}|~{}\mathcal{F}_{t,3})=o(1)$,
since critic converges at the faster time scale. Similar to Theorem 6, we have
$g^{2,i}(\theta_{t})=-G(\theta^{i}_{t})^{-1}\mathbb{E}_{s_{t}\sim
d_{\theta_{t}},a_{t}\sim\pi_{\theta_{t}}}(\tilde{\delta}^{i}_{t}\psi^{i}_{t}|\mathcal{F}_{t,3})$
that is continuous in $\theta^{i}_{t}$. The result follows by appealing to
Kushner-Clark lemma.

∎

###  4.3 Convergence of FIAP-MAN actor-critic algorithm

The critic convergence, the convergence of reward parameters, and objective
function estimate are the same as in Theorem 4. Thus, we provide proof for
actor convergence only. Like FI-MAN and AP-MAN algorithms, we again consider
the transformed problem; rewards replaced with costs. Therefore, we consider
the following recursion

$w^{i}_{t+1}=(1-\beta_{v,t})w^{i}_{t}-\beta_{v,t}G^{i^{-1}}_{t}\tilde{\delta}^{i}_{t}\psi^{i}_{t}.$
(50)

######  Theorem 9.

Under the assumptions X. 3 and X. 4, for each agent $i\in N$, with actor
parameters $\theta^{i}$, we have
$w_{t}^{i}\rightarrow-G(\theta^{i})^{-1}\mathbb{E}[\tilde{\delta}^{i}_{t,\theta}\psi^{i}_{t}]$
as $t\rightarrow\infty$ with probability one.

###### Proof.

To prove this, we first note that for each $i\in N$,
$sup_{t,\theta^{i},s_{t},a^{i}_{t}}||G_{t}^{i^{-1}}\tilde{\delta}^{i}_{t}\psi^{i}_{t}||<\infty$
with probability one. For the conditions given in Equation (10) there exists
$N_{0}$ such that for all $t\geq N_{0}$, $w^{i}_{t+1}$ is a convex combination
of $w^{i}_{t}$ and a uniformly bounded quantity,
$G^{i^{-1}}_{t}\tilde{\delta}^{i}_{t}\psi^{i}_{t}$. The overall sequence
$w^{i}_{t}$ of iterates, for any $w^{i}_{0}\in\mathbb{R}^{m_{i}}$ remains
bounded with probability one. One can re-write the Equation (50) as

${w}^{i}_{t+1}\leftarrow(1-\beta_{v,t})w^{i}_{t}-\beta_{v,t}G(\theta^{i})^{-1}\mathbb{E}[\tilde{\delta}^{i}_{t,\theta}\psi^{i}_{t}|\theta^{i}]-M^{3,i}_{t}+\beta_{v,t}\xi^{i}_{t+1,4}+\beta_{v,t}\xi^{i}_{t+1,5},$

where
$M^{3,i}_{t}=\beta_{v,t}G(\theta^{i})^{-1}(\tilde{\delta}^{i}_{t}\psi^{i}_{t}-\mathbb{E}[\tilde{\delta}^{i}_{t}\psi^{i}_{t}|\theta^{i}])$,
$\xi^{i}_{t+1,4}=(G(\theta^{i})^{-1}-G^{i^{-1}}_{t})\tilde{\delta}^{i}_{t}\psi^{i}_{t}$,
and
$\xi^{i}_{t+1,5}=G(\theta^{i})^{-1}\mathbb{E}[(\tilde{\delta}^{i}_{t,\theta}-\tilde{\delta}^{i}_{t})\psi_{t}^{i}|\theta^{i}]$
respectively. From Theorem 4 and 5 both $\xi^{i}_{t+1,4}$ and
$\xi^{i}_{t+1,5}$ are $o(1)$. Note that the sequence
$\\{\sum_{r=0}^{t-1}M^{3,i}_{r}\\}$ is a convergent martingale sequence. Let
$m_{T}=min\\{m\geq p|\sum_{r=p}^{m}\beta_{v,r}\geq T\\}$, then
$\sum_{r=p}^{m_{T}}\beta_{v,r}G(\theta^{i})^{-1}(\tilde{\delta}_{r}^{i}\psi_{r}^{i}-\mathbb{E}[\tilde{\delta}_{r}^{i}\psi_{r}^{i}|\theta^{i}_{r}])\rightarrow
0$ almost surely as $p\rightarrow\infty$. Next, consider the ODE associated
with Equation (50),

$\dot{w}^{i}=-w^{i}-G(\theta^{i})^{-1}\mathbb{E}[\tilde{\delta}^{i}_{t,\theta}\psi^{i}_{t}]=:g^{3,i}(w^{i}).$
(51)

Note that $g^{3,i}(w^{i})$ is Lipschitz continuous in $w^{i}$, and hence the
ODE (51) is well-posed. Let
$g^{3}_{\infty}(w^{i})=lim_{r\rightarrow\infty}\frac{g^{3}(rw^{i})}{r}=-w^{i}$.
For the ODE $\dot{w}^{i}=-w^{i}$ the origin is unique globally asymptotically
stable equilibrium with $V_{3}(w^{i})=w^{i^{\top}}w^{i}/2$ as the associated
Lyapunov function. Similar to Theorem 7 one can show that
$w(\theta^{i})=-G(\theta^{i})^{-1}\mathbb{E}[\tilde{\delta}^{i}_{t,\theta}\psi^{i}_{t}]$
is an asymptotically stable attractor for the ODE given in Equation (51). The
proof follows from Theorem 2.2 of [Borkar and Meyn, 2000].

∎

######  Theorem 10.

Under the assumptions X. 1 \- X. 5 the sequence $\\{\theta^{i}_{t}\\}$
obtained from the actor step of the FIAP-MAN algorithm converges a.s. to
asymptotically stable equilibrium set of the ODE

$\dot{\theta}^{i}=\hat{\Gamma}^{i}[-G(\theta^{i})^{-1}\mathbb{E}_{s_{t}\sim
d_{\theta},a_{t}\sim\pi_{\theta}}(\tilde{\delta}^{i}_{t,\theta}\psi^{i}_{t,\theta})],~{}~{}~{}\forall~{}i\in
N.$ (52)

The proof of the above theorem is similar to the Theorem 8. We avoid writing
it because of repetition.

######  Remark 5.

Though the ODEs corresponding to actor update in all MAN algorithms seem
similar, we emphasize that they come from three different algorithms, each
with a different critic update implicitly. Moreover, all the 3 MAN algorithms
have their way of updating the Fisher information matrix or/and advantage
parameters. Also, the objective function, $J(\theta)$, can have multiple
stationary points and local optima. Thus all the three algorithms can
potentially attain different optima, and this was clearly illustrated in our
comprehensive computational experiments in Section 5.1. Moreover, we also note
that the optimal value obtained from FI-MAN and FIAP-MAN are close to each
other, and AP-MAN and MAAC are also close. See also the discussion in Sections
3.4 and 3.5.

To validate the usefulness of our proposed MAN algorithms, we implement them
on a bi-lane traffic network and an abstract multi-agent RL model. The
detailed computational experiments follow in the next section.

##  5 Performance of algorithms in traffic network and abstract MARL models

This section provides comparative and comprehensive experiments in two
different setups. Firstly, we model traffic network control as a multi-agent
reinforcement learning problem. A similar model is available in [Bhatnagar,
2020] in a related but different context. Here, each traffic light is an
agent, and the collective objective of these traffic lights is to minimize the
average _network congestion_. Another setup that we consider is an abstract
multi-agent RL model with $15$ agents, $15$ states, and $2$ actions in each
state. The model, algorithm parameters, rewards, and the features used in the
linear function approximations are the same as given in [Dann et al., 2014,
Zhang et al., 2018].

All the computations are done in python 3.8 on a machine equipped with 8 GB
RAM and an Intel i5 processor. For the traffic network control, we use TraCI,
i.e., “Traffic Control Interface”. TraCI uses a TCP-based client/server
architecture to provide access to sumo-gui222The sumo-gui can be installed
using: https://www.eclipse.org/sumo/ in python, thereby sumo act as a server
[Krajzewicz et al., 2012]. For detailed documentation on TraCI, we refer to
https://sumo.dlr.de/docs/TraCI.html. We now describe the traffic network and
the arrival processes that we consider.

###  5.1 Performance of algorithms for traffic network controls

Consider the bi-lane traffic network as shown in Figure 1. The network
consists of $N_{1},N_{2},S_{1},S_{2},E_{1},E_{2},W_{1}$, and $W_{2}$ that act
as the source and the destination nodes. $T_{1},T_{2},T_{3}$, and $T_{4}$
represents the traffic lights and act as agents. All the edges in the network
are assumed to be of equal length. The agent’s objective is to find a traffic
signaling plan to minimize the overall network congestion. Note that the
congestion to each traffic light is private information and hence not
available to other traffic lights.

Figure 1: A bi-lane traffic network with four traffic lights
$T_{1},T_{2},T_{3},T_{4}$. All the other nodes
$N_{1},N_{2},S_{1},S_{2},E_{1},E_{2},W_{1}$, and $W_{2}$ act as the source and
destination nodes.

The sumo-gui requires the user to provide $T$, the total number of time steps
the simulation needs to be performed, and $N_{v}$, the number of vehicles used
in each simulation. As per the architecture of sumo-gui, vehicles arrive
uniformly from the interval $\\{1,2,\dots,T\\}$. Once a vehicle arrives, it
has to be assigned a source and a destination node. We assign the source node
to each incoming vehicle according to various distributions. Different arrival
patterns (ap) can be incorporated by considering different source-destination
node assignment distributions. We first describe the assignment of the source
node. We use two different arrival patterns to capture high or low number of
vehicles assigned to the source nodes in the network. Let $p_{s,ap}$ be the
probability that a vehicle is assigned a source node $s$ if arrival pattern is
$ap$. Table 1 gives probabilities, $p_{s,ap}$ for 2 arrival patterns
($ap\in\\{1,2\\}$) that we consider. The destination node is sampled uniformly
from the nodes except the source node. We assume that vehicles follow the
shortest path from the source node to the destination node. However, if there
are multiple paths with the same path length, then any one of them can be
chosen with uniform probability.

Source node $(s)$ | Arrival pattern $(ap)$
---|---
$ap=1$ | $ap=2$
$W_{1}$ | $\frac{3}{16}$ | $\frac{1}{28}$
$W_{2}$ | $\frac{1}{16}$ | $\frac{1}{28}$
$N_{1}$ | $\frac{1}{16}$ | $\frac{3}{14}$
$N_{2}$ | $\frac{3}{16}$ | $\frac{3}{14}$
$E_{1}$ | $\frac{3}{16}$ | $\frac{1}{28}$
$E_{2}$ | $\frac{1}{16}$ | $\frac{1}{28}$
$S_{1}$ | $\frac{1}{16}$ | $\frac{3}{14}$
$S_{2}$ | $\frac{3}{16}$ | $\frac{3}{14}$
Table 1: Probability $p_{s,ap}$ for all the nodes and arrival patterns. $ap=1$
assigns high probabilities to the nodes, $N_{2},S_{2}$ and $E_{1},W_{1}$.
$ap=2$ assigns high probabilities to all north and south nodes,
$N_{1},S_{1},N_{2},S_{2}$ and low probability to all east-west nodes,
$E_{1},E_{2},W_{1},W_{2}$.

In arrival pattern 1, i.e., $ap=1$, we have $p_{s,ap}$ higher for North-South
nodes $N_{2},S_{2}$, and East-West nodes $E_{1},W_{1}$. Thus, we expect to see
heavy congestion for traffic light $T_{2}$; almost same congestion for traffic
lights $T_{1}$ and $T_{4}$; and the least congestion for traffic light
$T_{3}$. For the arrival pattern 2, i.e., $ap=2$ more vehicles are assigned to
all the North-South nodes. So we expect that all the traffic lights will be
equally congested. For completeness, we now provide the distribution of the
number of vehicles assigned to a source node $s$ at time $t$ for a given
arrival pattern $ap$.

Let $N_{t}$ be the number of vehicles arrived at time $t$, and $N^{s}_{t}$ be
the number of vehicles assigned to source node $s$ at time $t$. Thus,
$N_{t}=\sum_{s}N^{s}_{t}$. Note that the arrivals are uniform in
$\\{0,1,\dots,T\\}$, so $N_{t}$ is a binomial random variable with parameters
$\left(N_{v},\frac{1}{T}\right)$. Therefore, we have

$\displaystyle\mathbb{P}(N_{t}=r)$
$\displaystyle=\binom{N_{v}}{r}\left(\frac{1}{T}\right)^{r}\left(1-\frac{1}{T}\right)^{N_{v}-r},\quad\forall~{}r=0,1,\cdots,N_{v}.$

Moreover, using the law of total probability, for all $ap~{}\in\\{1,2\\}$, we
obtain

$\displaystyle\mathbb{P}(N^{s}_{t}=k~{}|~{}ap)$
$\displaystyle=\binom{N_{v}}{k}\left(\frac{p_{s,ap}}{T}\right)^{k}\left(1-\frac{p_{s,ap}}{T}\right)^{N_{v}-k},~{}\forall~{}k=0,1,\cdots,N_{v},$
(53)

i.e., the distribution of $N_{t}^{s}$ for a given arrival pattern $ap$ is also
binomial with parameters $\left(N_{v},\frac{p_{s,ap}}{T}\right)$. For more
details see Appendix B.2.3.

In our experiments we take simulation time $T=180000$ seconds which is divided
into simulation cycle (called decision epoch) of $T_{c}=120$ seconds each.
Thus, there are 1500 decision epochs. The number of vehicles are taken as
$N_{v}=50000$. We now describe the decentralized MARL framework for the
traffic network shown in Figure 1.

####  5.1.1 Decentralized framework for traffic network control

In this section, we model the above traffic network control as a fully
decentralized MARL problem with traffic lights as agents,
$N=\\{T_{1},T_{2},T_{3},T_{4}\\}$. Let $E_{in}$ denote the set of edges
directed towards the traffic lights,

$E_{in}=\\{e_{1},e_{2},e_{12},e_{16},e_{3},e_{4},e_{9},e_{15},e_{8},e_{7},e_{11},e_{13},e_{5},e_{6},e_{10},e_{14}\\}.$

We assume that the maximum capacity of each lane in the network is $C=50$. The
state-space of the system consists of the number of vehicles in the lanes
belonging to $E_{in}$. Hence, the size of the state space is $50^{16}$. At
every decision epoch each traffic light follows one of the following traffic
signal plans for the next $T_{c}=120$ simulation steps.

  1. 1.

Equal green time of $\frac{T_{c}}{2}$ for both North-South and East-West lanes

  2. 2.

$\frac{3T_{c}}{4}$ green time for North-South and $\frac{T_{c}}{4}$ green time
for East-West lanes

  3. 3.

$\frac{T_{c}}{4}$ green time for North-South and $\frac{3T_{c}}{4}$ green time
for East-West lanes.

Thus the total number of actions available at each traffic light is
$3^{4}=81$. The rewards given to each agent is equal to the negative of the
average number of vehicles stopped at its corresponding traffic light. Note
that the rewards are privately available to each traffic light only. We aim to
maximize the expected time average of the globally averaged rewards, which is
equivalent to minimize the (time average of) number of stopped vehicles in the
system. Since the state space is huge $(50^{16})$, we use the linear function
approximation for the state value function and the reward function. The
approximate state value for state $s$ is $V(s;v)=v^{\top}\varphi(s)$, where
$\varphi(s)\in\mathbb{R}^{L},~{}L<<|\mathcal{S}|$, is the feature vector for
the state $s$. Moreover, the reward function is approximated as
${R}(s,a;\lambda)=\lambda^{\top}f(s,a)$ where
$f(s,a)\in\mathbb{R}^{M},~{}M<<|\mathcal{S}||\mathcal{A}|$ are the features
associated with each state-action pair $(s,a)$. Next, we describe the features
we are using in the experiments [Bhatnagar, 2020].

Let $x_{t}^{i}$ denote the number of vehicles in lane $e_{i}\in E_{in}$ at
time $t$. We normalize $x_{t}^{i}$ via maximum capacity of a lane, $C$ to
obtain $z_{t}^{i}=x_{t}^{i}/C$. We define $\xi(s)$ as a vector having
components containing $z_{t}^{i}$, as well as components with products of two
or three $z_{t}^{i}$’s. The product terms are of the form $z_{t}^{i}z_{t}^{j}$
and $z_{t}^{i}z_{t}^{j}z_{t}^{l}$ where all terms in the product correspond to
the same traffic light.

$\displaystyle\xi(s)$
$\displaystyle=\left(\begin{matrix}z_{t}^{1},&z_{t}^{2},&\cdots,&z_{t}^{16},&z_{t}^{1}z_{t}^{2},&\cdots,&z_{t}^{6}z_{t}^{5},&z_{t}^{1}z_{t}^{2}z_{t}^{12},&\cdots,&z_{t}^{5}z_{t}^{6}z_{t}^{10}\end{matrix}\right)$

The feature vector $\varphi(s)$ is defined as having all the components of
$\xi(s)$ along with an additional bias component, $1$. Thus,
$\varphi(s)=\left(\begin{matrix}1,&\xi(s)\end{matrix}\right)^{\top}$. The
length of $\xi(s)$ is $16+4\times(4^{2}+4^{3})=336$. Hence, the length of the
feature vector, $\varphi(s)$ is $L=1+336=337$. For each agent $i\in N$, we
parameterize the local policy $\pi^{i}(s,a^{i})$ using the Boltzmann
distribution as follows:

$\pi^{i}_{\theta^{i}}(s,a^{i})=\frac{\exp(q^{\top}_{s,a^{i}}\cdot\theta^{i})}{\sum_{b^{i}\in\mathcal{A}^{i}}\exp(q^{\top}_{s,b^{i}}\cdot\theta^{i})},$
(54)

where $q_{s,b^{i}}\in\mathbb{R}^{m_{i}}$ is the feature vector of dimension
same as $\theta^{i}$, for any $s\in\mathcal{S}$ and $b^{i}\in\mathcal{A}^{i}$,
for all $i\in N$. The feature vector $q_{s,a^{i}}$ for each $i\in N$ is given
by:

$\displaystyle q_{s,a^{i}}$
$\displaystyle=\left(\begin{matrix}1,&a^{i,1}\xi(s),&a^{i,2}\xi(s),&a^{i,3}\xi(s)\end{matrix}\right)^{\top},$

where $\xi(s)$ is defined as earlier, and $a^{i,j}$ are the binary numbers
defined as:

$\displaystyle a^{i,j}$ $\displaystyle=\begin{cases}1\quad\text{if signal plan
$j$ is selected in action $a^{i}$}\\\
0\quad\text{otherwise},\end{cases}~{}~{}\forall~{}i\in N.$

The length of $q_{s,a^{i}}$, i.e., $m_{i}=3\times 336+1=1009$. For the
Boltzmann policy function $\pi^{i}_{\theta^{i}}(s,a^{i})$ we have

$\nabla_{\theta^{i}}\log\pi^{i}_{\theta^{i}}(s,a^{i})=q_{s,a^{i}}-\sum_{b^{i}\in\mathcal{A}^{i}}\pi^{i}_{\theta^{i}}(s,b^{i})q_{s,b^{i}},$

where $\nabla_{\theta_{i}}\log\pi^{i}_{\theta_{i}}(s,a^{i})$ are the
compatible features as in the policy gradient Theorem [Sutton et al., 1999].
Note that the compatible features are same as the features associated to
policy, except normalized to be mean zero for each state. The features
$f(s,a)$ for the rewards function are taken in a similar way as $q_{s,a^{i}}$
for each $i\in N$, thus $M=4\times 3\times 336+1=4033$.

We implement all the 3 MAN algorithms and compared the average network
congestion with the MAAC algorithm. For all $i\in{N}$, the initial value of
parameters $\mu^{i}_{0}$, $\tilde{\mu}^{i}_{0}$, $v^{i}_{0}$,
$\tilde{v}^{i}_{0}$, $\lambda^{i}_{0}$, $\tilde{\lambda}^{i}_{0}$,
$\theta^{i}_{0}$, $w^{i}_{0}$ are taken as zero vectors of appropriate
dimensions. The Fisher information matrix inverse, $G_{0}^{i^{-1}}$ is
initialized to $I,~{}\forall~{}i\in N$. The critic and actor step sizes are
taken as $\beta_{v,t}=\frac{1}{(t+1)^{0.65}}$, and
$\beta_{\theta,t}=\frac{1}{(t+1)^{0.85}}$ respectively. Note that these step
sizes satisfy the conditions given in Equation (10). We assume that the
communication graph $\mathcal{G}_{t}$ is a complete graph at all time
instances $t$ and the consensus matrix is constant with
$c_{t}(i,j)=\frac{1}{4}$ for all pairs $i,j$ of agents. Although we do not use
the eligibility traces in the convergence analysis, we use them
($\lambda=0.25$ for TD($\lambda$) [Sutton and Barto, 2018]) to provide better
performance in case of function approximations. We believe that the
convergence of MAN algorithms while incorporating eligibility traces is easy
to follow, so we avoid them here. We now provide the performance of all the
algorithms in both the arrival patterns.

####  5.1.2 Performance of traffic network for arrival pattern 1

Recall, for arrival pattern 1 we assign high probability $p_{s,ap}$ to the
source nodes $N_{2},S_{2}$ and $E_{1},E_{2}$ and low probability to other
source nodes. Table 2 provides the average network congestion (averaged over
10 runs, and round off to 5 decimal places), standard deviation and 95%
confidence interval.

Algorithms |  | Avg network
---
congestion
Standard Deviation | Confidence Interval (95%)
MAAC | 14.01687 | 0.08405 | (13.96478, 14.06896)
FI-MAN | 12.02819 | 1.48071 | (11.11045, 12.94593)
AP-MAN | 14.07899 | 0.08266 | (14.02776, 14.13022)
FIAP-MAN | 11.28657 | 1.04137 | (10.64113, 11.93201)
Table 2: Average network congestion, standard deviation and 95% confidence
interval for arrival pattern 1. FIAP-MAN has $\approx$ 18%, and FI-MAN has
$\approx$ 14% less congestion than MAAC algorithm. The congestion for the AP-
MAN algorithm is almost the same as the MAAC algorithm with high confidence.

We observe an $\approx$ 18% reduction in average congestion for FIAP-MAN and
$\approx$ 14% reduction for FI-MAN algorithms compared to the MAAC algorithm.
These observations are theoretically justified in Section 3.4.

To show that these algorithms have attained the steady-state, we provide
average congestion, and the correction factor (CF), i.e., the 95% confidence
value which is defined as $CF=1.96\times\frac{std~{}dvn}{\sqrt{10}}$ for last
200 decision epochs in Table 8 of Appendix B.2.1. We observe that average
network congestion for the MAN algorithms are almost (up to 1st decimal) on
decreasing trend w.r.t. network congestion; however, this decay is prolonged
(0.1 fall in congestion in 200 epochs), suggesting that algorithms are
converging to a local minimum.

Thus, we see that algorithms involving the natural gradients dominate those
involving standard gradients. Figure 2 shows the (time) average network
congestion for single run (thus lower the better).

Figure 2: (Time) average network congestion for all the algorithms with
arrival pattern 1. The congestion is least for FIAP-MAN and FI-MAN algorithms.
However, MAAC and AP-MAN algorithms have almost the same congestion. Thus 2
(FI-MAN and FIAP-MAN) of the $3$ natural gradient-based algorithms find better
optima, and the third one (AP-MAN) is on par with the MAAC algorithm.
Moreover, for a few initial decision epochs $\approx$ 180, all the algorithms
have almost the same performance, but afterward, they find different
directions and end in different optima.

For almost $180$ decision epochs, all the algorithms have the same (time)
average network congestion. However, after 180 decision epochs, FI-MAN and
FIAP-MAN follow different paths and hence find different local minima as shown
in Theorem 3. We want to emphasize that the Theorem 3 is for maximization
framework. As mentioned above in Section 5.1.1, we are also maximizing the
globally average rewards, which is equivalent to minimizing the (time average
of) number of stopped vehicles.

#### Actor parameter comparison for arrival pattern 1

Recall, in Theorem 3 we show that under some conditions,
$J(\tilde{\theta}^{N}_{t+1})\geq J(\tilde{\theta}^{M}_{t+1})$ for all $t\geq
t_{0}$, and hence at each iterate the average network congestion in FI-MAN,
and FIAP-MAN algorithms are better than MAAC algorithm. To investigate this
further, we plot the norm of difference of the actor parameter of all the 3
MAN algorithms with MAAC algorithm for each agent. For traffic light $T_{1}$
(or agent 1) these differences are shown in Figure 3 (for other agents see
Figure 8 in Appendix B.2.1).

(a)

(b)

Figure 3: Norm of difference in the actor parameter of agent 1 for all the 3
MAN algorithms with MAAC algorithm for arrival pattern 1. Figure (a) is shown
for 350 decision epochs; to show that the differences in the actor parameter
are from decision epoch 2 itself, we zoom it in figure (b) in the left panel.
However, the significant differences are observed only after $\approx$ 180
epochs. This illustrates Theorem 3 and related discussions in Section 3.4.

We observe that all the 3 MAN algorithms pick up $\theta_{2}$ (i.e., the actor
parameter at decision epoch 2) that is different from that of the MAAC scheme
at varying degrees, with FI-MAN being a bit more ‘farther.’ However, a
significant difference is observed around decision epoch $\approx 180$. For
better understanding, the same graphs are also shown in the logarithmic scale
for agent 1 and agent 2 with arrival pattern 1 in Figure 4.

Figure 4: Norm of differences of the actor parameters for agents 1 and 2 with
traffic arrival pattern 1 in logarithmic scale illustrating Theorem 3 and
related discussions in Section 3.4.

We see that the norm difference is linearly increasing in FI-MAN and FIAP-MAN
algorithms, whereas it is almost flat for the AP-MAN algorithm. So, the
iterates of these $2$ algorithms are exponentially separating from those of
the MAAC algorithm. This again substantiates our analysis in Section 3.4.

Though we aim to minimize the network congestion, in Table 3 we also provide
the average congestion and the correction factor (CF) to each traffic light
for last decision epoch (Table 8 in Appendix B.2.1 shows these values for last
200 decision epochs). Expectedly, in all the algorithms, the average
congestion for traffic light $T_{2}$ is highest; almost same for traffic
lights $T_{1},T_{4}$; and least for traffic light $T_{3}$.

Algorithms | Congestion (Avg $\pm$ CF)
---|---
$T_{1}$ | $T_{2}$ | $T_{3}$ | $T_{4}$
MAAC | 3.733 $\pm$ 0.067 | 4.336 $\pm$ 0.050 | 2.249 $\pm$ 0.013 | 3.699 $\pm$ 0.040
FI-MAN | 2.613 $\pm$ 0.110 | 4.492 $\pm$ 0.868 | 2.359 $\pm$ 0.161 | 2.564 $\pm$ 0.038
AP-MAN | 3.748 $\pm$ 0.073 | 4.338 $\pm$ 0.046 | 2.247 $\pm$ 0.013 | 3.746 $\pm$ 0.039
FIAP-MAN | 2.711 $\pm$ 0.214 | 3.785 $\pm$ 0.371 | 1.907 $\pm$ 0.148 | 2.883 $\pm$ 0.147
Table 3: The average congestion and correction factor (CF) for each traffic
light for arrival pattern 1 (described in Section 5.1.2). CF is defined as
$1.96\times\frac{std~{}dvn}{\sqrt{10}}$.

####  5.1.3 Performance of traffic network for arrival pattern 2

Recall, in arrival pattern 1 nodes $N_{2},S_{2}$ and $E_{1},W_{1}$ are
assigned more $p_{s,ap}$. We now change the $p_{s,ap}$’s and consider arrival
pattern 2. Here the traffic origins $N_{1},N_{2},S_{1}$ and $S_{2}$ have
higher probabilities of being assigned a vehicle. Since $p_{s,ap}$ for all
these nodes is $\frac{3}{14}$, and for all other nodes it is $\frac{1}{28}$,
we expect that all the traffic lights will have almost the same average
congestion. This observation is reported in Appendix B.2.2. Table 4 present
the average network congestion (averaged over $10$ runs, and round off to 5
decimal places), standard deviation and 95% confidence interval for arrival
pattern 2.

Algorithms |  | Avg network
---
congestion
Standard deviation | Confidence Interval (95%)
MAAC | 13.64571 | 0.19755 | (13.52327, 13.76815)
FI-MAN | 10.16988 | 0.11877 | (10.09627, 10.24349)
AP-MAN | 13.77573 | 0.18925 | (13.65843, 13.89303)
FIAP-MAN | 10.19858 | 0.21248 | (10.06689, 10.33027)
Table 4: The average network congestion, standard deviation and 95% confidence
interval at last decision epoch for arrival pattern 2 (described in Section
5.1.3). FI-MAN and FIAP-MAN algorithms has $\approx$ 25% less average network
congestion than MAAC algorithm. The performance of AP-MAN algorithm is almost
similar to MAAC algorithm as shown in Theorem 3 and in Section 3.4.

We observe an $\approx$ 25% reduction in the average congestion with FI-MAN
and FIAP-MAN algorithms as compared to the MAAC algorithm. AP-MAN is on par
with the MAAC algorithm. This again shows the usefulness of the natural
gradient-based algorithms. As opposed to arrival pattern $1$ where FIAP-MAN
algorithm has slightly better performance than FI-MAN algorithm, in arrival
pattern $2$, both algorithms have almost similar average network congestion.
Moreover, the standard deviation in arrival pattern 1 is much higher than in
arrival pattern 2. Figure 5 shows the (time) average congestion for single
simulation run of all the algorithms.

Figure 5: (Time) average network congestion for arrival pattern 2. Again, for
few initial decision epochs $\approx$ 180 all the algorithms have almost same
performance, but afterwards they find different directions, and hence ends in
different optima.

#### Actor parameter comparison for arrival pattern 2

Similar to arrival pattern 1, in Figure 6 we plot the norm of the difference
for traffic light $T_{1}$ (for other traffic lights (agents) see Figure 9 of
Appendix B.2.2). For better understanding, the same graphs are also shown in
the logarithmic scale for agent 1 and agent 2 in Figure 7. Again, we see that
the norm difference is linearly increasing in FI-MAN and FIAP-MAN algorithms,
whereas it is almost flat for the AP-MAN algorithm. So, the iterates of these
$2$ algorithms are exponentially separating from the MAAC algorithm. This
again substantiates our analysis in Section 3.4. Moreover, we also compute the
average congestion and (simulation) correction factor for each traffic light.
Table 5 shows these values for last decision epoch (See Table 9 for last 200
decision epochs). As expected, the average congestion to each traffic light is
almost the same.

Algorithms | Congestion (Avg $\pm$ CF)
---|---
$T_{1}$ | $T_{2}$ | $T_{3}$ | $T_{4}$
MAAC | 3.481 $\pm$ 0.070 | 3.379 $\pm$ 0.034 | 3.348 $\pm$ 0.032 | 3.438 $\pm$ 0.033
FI-MAN | 2.532 $\pm$ 0.047 | 2.530 $\pm$ 0.040 | 2.519 $\pm$ 0.045 | 2.589 $\pm$ 0.045
AP-MAN | 3.511 $\pm$ 0.064 | 3.404 $\pm$ 0.032 | 3.376 $\pm$ 0.034 | 3.485 $\pm$ 0.033
FIAP-MAN | 2.566 $\pm$ 0.041 | 2.534 $\pm$ 0.034 | 2.543 $\pm$ 0.041 | 2.556 $\pm$ 0.036
Table 5: The average congestion and correction factor (CF) for each traffic
light for arrival pattern 2 (described in Section 5.1.3). CF is defined as
$1.96\times\frac{std~{}dvn}{\sqrt{10}}$. For more details see Table 9.

(a)

(b)

Figure 6: Norm of difference in the actor parameter of agent 1 for all the 3
MAN algorithms with MAAC algorithm. Figure (a) is shown for 350 decision
epochs; to show that the differences in the actor parameter are from decision
epoch 2 itself, we zoom it in Figure (b). However, the significant differences
are observed only after $\approx$ 180 epochs. This illustrates Theorem 3 and
related discussions in Section 3.4.

Figure 7: Norm of differences of the actor parameter for agents 1 and 2 with
traffic arrival pattern 2 in logarithmic scale illustrating Theorem 3 and
related discussions in Section 3.4.

We now present another computational experiment where we consider an abstract
MARL with $n=15$ agents. The model, algorithm parameters, including transition
probabilities, rewards, and features for state value function, and rewards are
the same as given in [Dann et al., 2014, Zhang et al., 2018]

###  5.2 Performance of algorithms in abstract MARL model

The abstract MARL model that we consider consists of $n=15$ agents and
$|\mathcal{S}|=15$ states. Each agent $i\in N$ is endowed with the binary
valued actions $\mathcal{A}^{i}\in\\{0,1\\}$. Therefore, the total number of
actions are $2^{15}$. Each element of the transition probability is a random
number uniformly generated from the interval $[0,1]$. These values are
normalized to incorporate the stochasticity. To ensure the ergodicity we add a
small constant $10^{-5}$ to each entry of the transition matrix. The mean
reward $R^{i}(s,a)$ are sampled uniformly from the interval $[0,4]$ for each
agent $i\in N$, and for each state-action pair $(s,a)$. The instantaneous
rewards $r^{i}_{t}$ are sampled uniformly from the interval
$[R^{i}(s,a)-0.5,R^{i}(s,a)+0.5]$. We parameterize the policy using the
Boltzmann distribution as given in Equation (54) with
$m_{i}=5,~{}\forall~{}i\in N$. All the feature vectors (for the state value
and the reward functions) are sampled uniformly from the set $[0,1]$ of
suitable dimensions. More details of the multi-agent model are available in
Appendix B.1.

We compare all the 3 MAN actor-critic algorithms with the MAAC algorithm. We
observe that the globally averaged return from all the algorithms is almost
close to each other (for details, see Table 6 of Appendix B.1). To provide
more details, we compute the relative $V$ values for each agent $i\in N$ that
is defined as $V_{\theta}(s;v^{i})=v^{i^{\top}}\varphi(s)$; this way of
comparison of MARL algorithms was earlier used by [Zhang et al., 2018]. Thus,
the higher the value, the better is the algorithm. The relative values
corresponding to the FI-MAN and FIAP-MAN algorithms are more than the MAAC
algorithm almost for all agents, suggesting again that the natural gradient-
based algorithms are better than the standard gradient ones (as far as the
relative values are concerned). The detailed observations are available in
Appendix B.1.

##  6 Related work

Reinforcement learning has been extensively studied and explored by
researchers because of its varied applications and usefulness in many real-
world applications [Fax and Murray, 2004, Corke et al., 2005, Dall’Anese et
al., 2013]. Single-agent reinforcement learning models are well explained in
many works including [Bertsekas, 1995, Sutton and Barto, 2018, Bertsekas,
2019]. The average reward reinforcement learning algorithms are available in
[Mahadevan, 1996, Dewanto et al., 2020].

Various algorithms to compute the optimal policy for single-agent RL are
available; these are mainly classified as off-policy and on-policy algorithms
in literature [Sutton and Barto, 2018]. Moreover, because of the large state
and action space, it is often helpful to consider the function approximations
of the state value functions [Sutton et al., 1999]. To this end, actor-critic