algorithms with function approximations are presented in [Konda and
Tsitsiklis, 2000]. In actor-critic algorithms, the actor updates the policy
parameters, and the critic evaluates the policy’s value for the actor
parameters until convergence. The convergence of linear architecture in actor-
critic methods is known. The algorithm in [Konda and Tsitsiklis, 2000] uses
the standard gradient while estimating the objective function. However, as
mentioned in Section 2, we outlined some drawbacks of using standard gradients
[Ratliff, 2013, Martens, 2020].

To the best of our knowledge, the idea of natural gradients stems from the
work of [Amari and Douglas, 1998]. Afterward, it has been expanded to learning
setup in [Amari, 1998]. For recent developments and work on natural gradients
we refer to [Martens, 2020]. Some recent overviews of natural gradients are
available in [Bottou et al., 2018] and lecture slides by Roger
Grosse333https://csc2541-f17.github.io/slides/lec05a.pdf. The policy gradient
theorem involving the natural gradients is explored in [Kakade, 2001]. For the
discounted reward [Agarwal et al., 2021, Mei et al., 2020] recently showed
that despite the non-concavity in the objective function, the policy gradient
methods under tabular setting with softmax policy characterization find the
global optima. However, such a result is not available for average reward
criteria with actor-critic methods and the general class of policy. Moreover,
we also see in our computations in Section 5.1 that MAN algorithms are
stabilizing at different local optima. Actor-critic methods involving the
natural gradients for single-agent are available in [Peters and Schaal, 2008,
Bhatnagar et al., 2009a]. On the contrary, we deal with the multi-agent setup
where all agents have private rewards but have a common objective. For a
comparative survey of the MARL algorithms, we refer to [Busoniu et al., 2008,
Tuyls and Weiss, 2012, Zhang et al., 2021b].

The MARL algorithms given in [Zhang et al., 2021b] are majorly centralized,
and hence relatively slow. However, in many situations [Corke et al., 2005,
Dall’Anese et al., 2013] deploying a centralized agent is inefficient and
costly. Recently, [Zhang et al., 2018] gave two different actor-critic
algorithms in a fully decentralized setup; one based on approximating the
state-action value function and the other approximating the state value
function. Another work in the same direction is available in [Heredia and Mou,
2019, Suttle et al., 2020, Zhang et al., 2021a, Mathkar and Borkar, 2016]. In
particular, for distributed stochastic approximations, authors in [Mathkar and
Borkar, 2016] introduced and analyzed a non-linear gossip-based distributed
stochastic approximation scheme. We use some proof techniques as part of
consensus updates from it. We build on algorithm 2 of the [Zhang et al., 2018]
and incorporate the natural gradients into it. The algorithms that we propose
use the natural gradients as in [Bhatnagar et al., 2009a]. We propose three
algorithms incorporating natural gradients into multi-agent RL based on
Fisher’s information matrix inverse, approximation of advantage parameters, or
both. Using the ideas of stochastic approximation available in [Borkar and
Meyn, 2000, Borkar, 2009, Kushner and Clark, 2012], we prove the convergence
of all the proposed algorithms.

##  7 Discussion

This paper proposes three multi-agent natural actor-critic (MAN) reinforcement
learning algorithms. Instead of using a central controller for taking action,
our algorithms use the consensus matrix and are fully decentralized. These MAN
algorithms majorly use the Fisher information matrix and the advantage
function approximations. We show the convergence of all the three MAN
algorithms, possibly to different local optima.

We prove that a deterministic equivalent of the natural gradient-based
algorithm dominates that of the MAAC algorithm under some conditions. It
follows by leveraging a fundamental property of the Fisher information matrix
that we show: the minimum singular value is within the reciprocal of the
dimension of the policy parameterization space.

The Fisher information matrix in the natural gradient-based algorithms
captures the KL divergence curvature between the policies at consecutive
iterates. Indeed, we show that the KL divergence is proportional to the
objective function’s gradient. The use of natural gradients offered a _new
representation_ to the objective function’s gradient in the prediction space
of policy distributions which improved the search for better policies.

To demonstrate the usefulness of our algorithm, we empirically evaluate them
on a bi-lane traffic network model. The goal is to minimize the overall
congestion in the network in a fully decentralized fashion. Sometimes the MAN
algorithms can reduce the network congestion by almost $\approx 25\%$ compared
to the MAAC algorithm. One of our natural gradient-based algorithms, AP-MAN,
is on par with the MAAC algorithm. Moreover, we also consider an abstract MARL
with $n=15$ agents; again, the MAN algorithms are at least as good as the MAAC
algorithm with high confidence.

We now mention some of the further possibilities. Firstly, some assumptions on
the communication network can be relaxed [Thoppe and Kumar, 2021]. A careful
study of the trade-off between extra per iterate computation versus the gain
in the objective function value of the learned MARL policy obtained by these
MAN algorithms would be useful. It is in the context of a similar phenomenon
in optimization algorithms [Bottou et al., 2018], [Nocedal and Wright, 2006]
and other computational sciences.

Moreover, further understanding of the natural gradients and its key
ingredient, the Fisher information matrix $G(\theta)$, is needed in their role
as learning representations. Our uniform bound on the smallest singular value
of $G(\theta)$ and its role in the dominance of deterministic MAN algorithms
are initial results in these directions. More broadly, various learning
representations for RL like natural gradients and others are further
possibilities.

## References

  * [Agarwal et al., 2021] Agarwal, A., Kakade, S. M., Lee, J. D., and Mahajan, G. (2021).  On the theory of policy gradient methods: Optimality, approximation, and distribution shift.  Journal of Machine Learning Research, 22(98):1–76.
  * [Amari, 1998] Amari, S. I. (1998).  Natural gradient works efficiently in learning.  Neural computation, 10(2):251–276.
  * [Amari and Douglas, 1998] Amari, S. I. and Douglas, S. C. (1998).  Why natural gradient?  In Proceedings of the 1998 IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP’98 (Cat. No. 98CH36181), volume 2, pages 1213–1216. IEEE.
  * [Aoki, 2016] Aoki, M. (2016).  Optimization of stochastic systems: topics in discrete-time systems.  Elsevier.
  * [Bagnell and Schneider, 2003] Bagnell, J. A. and Schneider, J. (2003).  Covariant policy search.  In Proceedings of the 18th International Joint Conference on Artificial intelligence, pages 1019–1024.
  * [Bertsekas, 1995] Bertsekas, D. P. (1995).  Dynamic programming and optimal control, volume 1.  Athena scientific Belmont, MA.
  * [Bertsekas, 1997] Bertsekas, D. P. (1997).  Nonlinear Programming.  Athena scientific, 3rd edition.
  * [Bertsekas, 2019] Bertsekas, D. P. (2019).  Reinforcement learning and optimal control.  Athena scientific.
  * [Bhatnagar, 2020] Bhatnagar, S. (2020).  Single and multi-agent reinforcement learning in changing environments.  Master’s thesis, Industrial Engineering and Operations Research, IIT Bombay.
  * [Bhatnagar et al., 2009a] Bhatnagar, S., Sutton, R. S., Ghavamzadeh, M., and Lee, M. (2009a).  Natural actor–critic algorithms.  Automatica, 45(11):2471–2482.
  * [Bhatnagar et al., 2009b] Bhatnagar, S., Sutton, R. S., Ghavamzadeh, M., and Lee, M. (2009b).  Natural actor–critic algorithms. University of Alberta Department of Computing Science Technical Report TR 09-10.
  * [Bianchi et al., 2013] Bianchi, P., Fort, G., and Hachem, W. (2013).  Performance of a distributed stochastic approximation algorithm.  IEEE Transactions on Information Theory, 59(11):7405–7418.
  * [Borkar, 2009] Borkar, V. S. (2009).  Stochastic approximation: a dynamical systems viewpoint, volume 48.  Springer.
  * [Borkar and Meyn, 2000] Borkar, V. S. and Meyn, S. P. (2000).  The ode method for convergence of stochastic approximation and reinforcement learning.  SIAM Journal on Control and Optimization, 38(2):447–469.
  * [Bottou et al., 2018] Bottou, L., Curtis, F. E., and Nocedal, J. (2018).  Optimization methods for large-scale machine learning.  SIAM Review, 60(2):223–311.
  * [Boyd et al., 2006] Boyd, S., Ghosh, A., Prabhakar, B., and Shah, D. (2006).  Randomized gossip algorithms.  IEEE Transactions on Information Theory, 52(6):2508–2530.
  * [Busoniu et al., 2008] Busoniu, L., Babuska, R., and De Schutter, B. (2008).  A comprehensive survey of multiagent reinforcement learning.  IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews), 38(2):156–172.
  * [Corke et al., 2005] Corke, P., Peterson, R., and Rus, D. (2005).  Networked robots: Flying robot navigation using a sensor net.  In Robotics Research. The Eleventh International Symposium, pages 234–243. Springer.
  * [Dall’Anese et al., 2013] Dall’Anese, E., Zhu, H., and Giannakis, G. B. (2013).  Distributed optimal power flow for smart microgrids.  IEEE Transactions on Smart Grid, 4(3):1464–1475.
  * [Dann et al., 2014] Dann, C., Neumann, G., and Peters, J. (2014).  Policy evaluation with temporal differences: A survey and comparison.  Journal of Machine Learning Research, 15:809–883.
  * [Dewanto et al., 2020] Dewanto, V., Dunn, G., Eshragh, A., Gallagher, M., and Roosta, F. (2020).  Average-reward model-free reinforcement learning: a systematic review and literature mapping.  arXiv preprint arXiv:2010.08920.
  * [Doan et al., 2021] Doan, T. T., Maguluri, S. T., and Romberg, J. (2021).  Finite-time performance of distributed temporal-difference learning with linear function approximation.  SIAM Journal on Mathematics of Data Science, 3(1):298–320.
  * [Fax and Murray, 2004] Fax, J. A. and Murray, R. M. (2004).  Information flow and cooperative control of vehicle formations.  IEEE Transactions on Automatic Control, 49(9):1465–1476.
  * [Folland, 1999] Folland, G. B. (1999).  Real analysis: modern techniques and their applications, volume 40.  John Wiley & Sons.
  * [Grondman et al., 2012] Grondman, I., Busoniu, L., Lopes, G. A., and Babuska, R. (2012).  A survey of actor-critic reinforcement learning: Standard and natural policy gradients.  IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews), 42(6):1291–1307.
  * [Heredia and Mou, 2019] Heredia, P. C. and Mou, S. (2019).  Distributed multi-agent reinforcement learning by actor-critic method.  IFAC-PapersOnLine, 52(20):363–368.
  * [Horn and Johnson, 2012] Horn, R. A. and Johnson, C. R. (2012).  Matrix analysis.  Cambridge university press.
  * [Kakade, 2001] Kakade, S. M. (2001).  A natural policy gradient.  Advances in Neural Information Processing Systems, 14.
  * [Konda and Tsitsiklis, 2000] Konda, V. R. and Tsitsiklis, J. N. (2000).  Actor-critic algorithms.  In Advances in Neural Information Processing Systems, pages 1008–1014. Citeseer.
  * [Krajzewicz et al., 2012] Krajzewicz, D., Erdmann, J., Behrisch, M., and Bieker, L. (2012).  Recent development and applications of sumo-simulation of urban mobility.  International Journal on Advances in Systems and Measurements, 5(3&4).
  * [Kushner and Yin, 2003] Kushner, H. and Yin, G. G. (2003).  Stochastic approximation and recursive algorithms and applications, volume 35.  Springer Science & Business Media.
  * [Kushner and Clark, 2012] Kushner, H. J. and Clark, D. S. (2012).  Stochastic approximation methods for constrained and unconstrained systems, volume 26.  Springer Science & Business Media.
  * [Mahadevan, 1996] Mahadevan, S. (1996).  Average reward reinforcement learning: Foundations, algorithms, and empirical results.  Machine Learning, 22(1):159–195.
  * [Martens, 2020] Martens, J. (2020).  New insights and perspectives on the natural gradient method.  Journal of Machine Learning Research, 21(146):1–76.
  * [Mathkar and Borkar, 2016] Mathkar, A. S. and Borkar, V. S. (2016).  Nonlinear gossip.  SIAM Journal on Control and Optimization, 54(3):1535–1557.
  * [Mei et al., 2020] Mei, J., Xiao, C., Szepesvari, C., and Schuurmans, D. (2020).  On the global convergence rates of softmax policy gradient methods.  In International Conference on Machine Learning, pages 6820–6829. PMLR.
  * [Metivier and Priouret, 1984] Metivier, M. and Priouret, P. (1984).  Applications of a Kushner and Clark lemma to general classes of stochastic algorithms.  IEEE Transactions on Information Theory, 30(2):140–151.
  * [Nedic et al., 2017] Nedic, A., Olshevsky, A., and Shi, W. (2017).  Achieving geometric convergence for distributed optimization over time-varying graphs.  SIAM Journal on Optimization, 27(4):2597–2633.
  * [Nedic and Ozdaglar, 2009] Nedic, A. and Ozdaglar, A. (2009).  Distributed subgradient methods for multi-agent optimization.  IEEE Transactions on Automatic Control, 54(1):48–61.
  * [Neveu, 1975] Neveu, Jacques translated by Speed, T. (1975).  Discrete-parameter martingales, volume 10.  North-Holland Amsterdam.
  * [Nocedal and Wright, 2006] Nocedal, J. and Wright, S. (2006).  Numerical optimization.  Springer Science & Business Media.
  * [Patchell and Jacobs, 1971] Patchell, J. and Jacobs, O. (1971).  Separability, neutrality and certainty equivalence.  International Journal of Control, 13(2):337–342.
  * [Peters and Schaal, 2008] Peters, J. and Schaal, S. (2008).  Natural actor-critic.  Neurocomputing, 71(7-9):1180–1190.
  * [Peters et al., 2003] Peters, J., Vijayakumar, S., and Schaal, S. (2003).  Reinforcement learning for humanoid robotics.  In 3rd IEEE-RAS International Conference on Humanoid Robots (ICHR 2003), pages 1–20.
  * [Puterman, 2014] Puterman, M. L. (2014).  Markov decision processes: discrete stochastic dynamic programming.  John Wiley & Sons.
  * [Ratliff, 2013] Ratliff, N. (2013).  Information geometry and natural gradients. Available at https://ipvs.informatik.uni-stuttgart.de/mlr/wp-content/uploads/2015/01/mathematics_for_intelligent_systems_lecture12_notes_I.pdf. Last accessed August 20, 2021.
  * [Sherman and Morrison, 1950] Sherman, J. and Morrison, W. J. (1950).  Adjustment of an inverse matrix corresponding to a change in one element of a given matrix.  The Annals of Mathematical Statistics, 21(1):124–127.
  * [Suttle et al., 2020] Suttle, W., Yang, Z., Zhang, K., Wang, Z., Başar, T., and Liu, J. (2020).  A multi-agent off-policy actor-critic algorithm for distributed reinforcement learning.  IFAC-PapersOnLine, 53(2):1549–1554.
  * [Sutton and Barto, 2018] Sutton, R. S. and Barto, A. G. (2018).  Reinforcement learning: An introduction.  MIT press.
  * [Sutton et al., 1999] Sutton, R. S., McAllester, D. A., Singh, S. P., Mansour, Y., et al. (1999).  Policy gradient methods for reinforcement learning with function approximation.  In NIPS, volume 99, pages 1057–1063. Citeseer.
  * [Thoppe and Borkar, 2019] Thoppe, G. and Borkar, V. (2019).  A concentration bound for stochastic approximation via alekseev’s formula.  Stochastic Systems, 9(1):1–26.
  * [Thoppe and Kumar, 2021] Thoppe, G. C. and Kumar, B. (2021).  A law of iterated logarithm for multi-agent reinforcement learning.  Advances in Neural Information Processing Systems, 34.
  * [Tuyls and Weiss, 2012] Tuyls, K. and Weiss, G. (2012).  Multiagent learning: Basics, challenges, and prospects.  AI Magazine, 33(3).
  * [Xiao et al., 2005] Xiao, L., Boyd, S., and Lall, S. (2005).  A scheme for robust distributed sensor fusion based on average consensus.  In IPSN 2005. Fourth International Symposium on Information Processing in Sensor Networks, 2005., pages 63–70. IEEE.
  * [Zhang et al., 2021a] Zhang, K., Yang, Z., and Başar, T. (2021a).  Decentralized multi-agent reinforcement learning with networked agents: recent advances.  Frontiers of Information Technology & Electronic Engineering, 22(6):802–814.
  * [Zhang et al., 2021b] Zhang, K., Yang, Z., and Başar, T. (2021b).  Multi-agent reinforcement learning: A selective overview of theories and algorithms.  Handbook of Reinforcement Learning and Control, pages 321–384.
  * [Zhang et al., 2018] Zhang, K., Yang, Z., Liu, H., Zhang, T., and Basar, T. (2018).  Fully decentralized multi-agent reinforcement learning with networked agents.  In International Conference on Machine Learning, pages 5872–5881. PMLR.

##  Appendix A Proof of theorems and lemmas

In this section, we provide proof of some important theorems and lemmas stated
in the main paper.

###  A.1 Proof of Theorem 1 [Zhang et al., 2018]

Recall Theorem 1: 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)].$

###### Proof.

The proof is a suitable extension of the policy gradient theorem for single
agent RL [Sutton et al., 1999] which says

$\displaystyle\nabla_{\theta}J(\theta)$ $\displaystyle=$
$\displaystyle\mathbb{E}_{s\sim
d_{\theta},a\sim\pi_{\theta}}[\nabla_{\theta}\log\pi_{\theta}(s,a)\cdot
Q_{\theta}(s,a)],$ (55) $\displaystyle=$
$\displaystyle\sum_{s\in\mathcal{S}}d_{\theta}(s)\sum_{a\in\mathcal{A}}\pi_{\theta}(s,a)\left[\nabla_{\theta}\sum_{i\in
N}\log\pi^{i}_{\theta^{i}}(s,a^{i})\right]\cdot Q_{\theta}(s,a).$

The second equality holds because for the multi-agent setup,
$\pi_{\theta}=\prod_{i\in N}\pi_{\theta^{i}}^{i}(s,a^{i})$. Therefore, the
gradient of the objective function $J(\theta)$ with respect to $\theta^{i}$ is
given by

$\nabla_{\theta^{i}}J(\theta)=\sum_{s\in\mathcal{S}}d_{\theta}(s)\sum_{a\in\mathcal{A}}\pi_{\theta}(s,a)\left[\nabla_{\theta^{i}}\log\pi^{i}_{\theta^{i}}(s,a^{i})\right]\cdot
Q_{\theta}(s,a).$ (56)

Moreover, we have
$\sum_{a^{i}\in\mathcal{A}^{i}}\pi^{i}_{\theta^{i}}(s,a^{i})=1$, and hence
$\nabla_{\theta^{i}}\left[\sum_{a^{i}\in\mathcal{A}^{i}}\pi^{i}_{\theta^{i}}(s,a^{i})\right]=0$.
This implies, $\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 let $a^{-i}=(a^{1},\dots,a^{i-1},a^{i+1},\dots,a^{n})$ be the joint action
of all the agents except agent $i\in N$, and let
$\mathcal{A}^{-1}=\prod_{j\neq i}\mathcal{A}^{j}$. Thus, for any function
$\Lambda:\mathcal{S}\times\mathcal{A}^{-i}\rightarrow\mathbb{R}$ that doesn’t
depend on $a^{i}$, we have

$\displaystyle\sum_{a\in\mathcal{A}}\pi_{\theta}(s,a)\left[\nabla_{\theta^{i}}\log\pi^{i}_{\theta^{i}}(s,a^{i})\right]\cdot\Lambda(s,a^{-i})$
$\displaystyle=\sum_{a^{-i}\in\mathcal{A}^{-i}}\Lambda(s,a^{-i})\cdot\left[\prod_{j\in
N,j\neq
i}\pi^{j}_{\theta^{j}}(s,a^{j})\right]\cdot\left[\sum_{a^{i}\in\mathcal{A}^{i}}\nabla_{\theta^{i}}\pi^{i}_{\theta^{i}}(s,a^{i})\right]$
(57) $\displaystyle=0.$

Thus, replacing $\Lambda$ in above equation by value function $V_{\theta}(s)$
we have first equality of theorem, and replacing it by
$\tilde{V}_{\theta}^{i}(s,a^{-i})$ we obtain the second equality.

∎

###  A.2 Stationary points of optimization problems in the reward function
parameterization

Recall the two optimization problems are:

$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}.$
(OP 1)

$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},$
(OP 2)

Taking the first derivative of the objective function in optimization problem
(OP 1) w.r.t. $\lambda$, we have:

$\displaystyle-2\times\sum_{s\in\mathcal{S},a\in\mathcal{A}}\tilde{d}_{\theta}(s,a)[\bar{R}(s,a)-\bar{R}(s,a;\lambda)]\times\nabla_{\lambda}\bar{R}(s,a;\lambda),$
$\displaystyle=$
$\displaystyle-2\times\sum_{s\in\mathcal{S},a\in\mathcal{A}}\tilde{d}_{\theta}(s,a)\left[\frac{1}{n}\sum_{i\in{N}}R^{i}(s,a)-\bar{R}(s,a;\lambda)\right]\times\nabla_{\lambda}\bar{R}(s,a;\lambda),$
$\displaystyle=$
$\displaystyle-\frac{2}{n}\times\sum_{s\in\mathcal{S},a\in\mathcal{A}}\tilde{d}_{\theta}(s,a)\left[\sum_{i\in{N}}R^{i}(s,a)-n\cdot\bar{R}(s,a;\lambda)\right]\times\nabla_{\lambda}\bar{R}(s,a;\lambda),$
$\displaystyle=$
$\displaystyle-\frac{2}{n}\times\sum_{s\in\mathcal{S},a\in\mathcal{A}}\tilde{d}_{\theta}(s,a)\left[\sum_{i\in{N}}\left(R^{i}(s,a)-\bar{R}(s,a;\lambda)\right)\right]\times\nabla_{\lambda}\bar{R}(s,a;\lambda).$

Ignoring the factor $\frac{1}{n}$, the above equation we exactly have the
first derivative of the objective function in OP 2. Thus, both the
optimization problems have the same stationary points. Hence, OP 1 is an
equivalent characterization of OP 2.

###  A.3 Proof of Lemma 2

Recall 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}$, i.e.,

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

###### Proof.

First recall that the Fisher matrix is defined as
$G(\theta)=\mathbb{E}[\psi\psi^{\top}]$. Also, the matrix $G(\theta)$ is
symmetric and positive definite. Let $\lambda_{\min}(G(\theta))$ be the
minimum eigenvalue of $G(\theta)$. Thus,
$\sigma_{\min}(G(\theta))=\sqrt{\lambda_{\min}(G(\theta)G(\theta)^{\top})}=\sqrt{\lambda_{\min}(G^{2}(\theta))}=\sqrt{\lambda_{\min}^{2}(G(\theta))}=\lambda_{\min}(G(\theta))$.

$\displaystyle\lambda_{\min}(G(\theta))$ $\displaystyle\leq$
$\displaystyle\frac{1}{m}\sum_{j=1}^{m}\lambda_{j}(G(\theta))=\frac{1}{m}tr(G(\theta))$
$\displaystyle=$
$\displaystyle\frac{1}{m}tr(\mathbb{E}[\psi\psi^{\top}])=\frac{1}{m}\mathbb{E}[tr(\psi\psi^{\top})]$
$\displaystyle=$ $\displaystyle\frac{1}{m}\mathbb{E}[||\psi||^{2}]$
$\displaystyle\leq$ $\displaystyle\frac{1}{m}.$

This ends the proof.

∎

###  A.4 Proof of Lemma 4

Recall the 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],$ (59)

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

###### Proof.

Recall, KL divergence is defined as

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

This ends the proof.

∎

###  A.5 Proof of Lemma 5

Recall the 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)].$
(60)

###### Proof.

Recall,
$KL(\pi_{\theta_{t}}(\cdot,\cdot)||\pi_{\theta_{t}+\Delta\theta_{t}}(\cdot,\cdot))$
for the Boltzmann policy is given in Lemma 4. Thus, $\nabla
KL(\pi_{\theta_{t}}(\cdot,\cdot)||\pi_{\theta_{t}+\Delta\theta_{t}}(\cdot,\cdot))$
is

$\displaystyle=$
$\displaystyle\nabla\mathbb{E}\left[\log\left(\sum_{b\in\mathcal{A}}\pi_{\theta_{t}}(s,b)\cdot\exp(\Delta
q_{s,ba}^{\top}\Delta\theta_{t})\right)\right]$ $\displaystyle=$
$\displaystyle\mathbb{E}\left[\nabla\log\left(\sum_{b\in\mathcal{A}}\pi_{\theta_{t}}(s,b)\cdot\exp(\Delta
q_{s,ba}^{\top}\Delta\theta_{t})\right)\right]~{}~{}(\because~{}\mathcal{A}~{}is~{}finite)$
$\displaystyle=$
$\displaystyle\mathbb{E}\left[\frac{1}{\sum_{b\in\mathcal{A}}\pi_{\theta_{t}}(s,b)\cdot\exp(\Delta
q_{s,ba}^{\top}\Delta\theta_{t})}\cdot\sum_{b\in\mathcal{A}}\pi_{\theta_{t}}(s,b)\cdot\Delta
q_{s,ba}\cdot\exp(\Delta q_{s,ba}^{\top}\Delta\theta_{t})\right]$
$\displaystyle=$
$\displaystyle\mathbb{E}\left[\sum_{b\in\mathcal{A}}\pi_{\theta_{t}}(s,b)\cdot\Delta
q_{s,ba}\cdot\left(\frac{\exp(\Delta
q_{s,ba}^{\top}\Delta\theta_{t})}{\sum_{c\in\mathcal{A}}\pi_{\theta_{t}}(s,c)\cdot\exp(\Delta
q_{s,ca}^{\top}\Delta\theta_{t})}\right)\right]$ $\displaystyle=$
$\displaystyle\mathbb{E}\left[\sum_{b\in\mathcal{A}}\Delta
q_{s,ba}\cdot\left(\frac{\pi_{\theta_{t}}(s,b)\cdot\exp(\Delta
q_{s,ba}^{\top}\Delta\theta_{t})}{\sum_{c\in\mathcal{A}}\pi_{\theta_{t}}(s,c)\cdot\exp(\Delta
q_{s,ca}^{\top}\Delta\theta_{t})}\right)\right]$ $\displaystyle=$
$\displaystyle\mathbb{E}\left[\sum_{b\in\mathcal{A}}\Delta
q_{s,ba}\cdot\left(\frac{\frac{\exp(q^{\top}_{s,b}\theta_{t})}{\sum_{e\in\mathcal{A}}\exp(q^{\top}_{s,e}\theta_{t})}\cdot\frac{\exp(q^{\top}_{s,b}\Delta\theta_{t})}{\exp(q^{\top}_{s,a}\Delta\theta_{t})}}{\sum_{c\in\mathcal{A}}\frac{\exp(q^{\top}_{s,c}\theta_{t})}{\sum_{d\in\mathcal{A}}\exp(q^{\top}_{s,d}\theta_{t})}\cdot\frac{\exp(q^{\top}_{s,c}\Delta\theta_{t})}{\exp(q^{\top}_{s,a}\Delta\theta_{t})}}\right)\right]$
$\displaystyle=$ $\displaystyle\mathbb{E}\left[\sum_{b\in\mathcal{A}}\Delta
q_{s,ba}\cdot\left(\frac{\exp(q^{\top}_{s,b}(\theta_{t}+\Delta\theta_{t}))}{\sum_{c\in\mathcal{A}}\exp(q^{\top}_{s,c}(\theta_{t}+\Delta\theta_{t}))}\right)\right]$
$\displaystyle=$
$\displaystyle\mathbb{E}\left[\sum_{b\in\mathcal{A}}(q^{\top}_{s,b}-q^{\top}_{s,a})\cdot\pi_{\theta_{t}+\Delta\theta_{t}}(s,b)\right]$
$\displaystyle=$
$\displaystyle-\mathbb{E}\left[q^{\top}_{s,a}-\sum_{b\in\mathcal{A}}q^{\top}_{s,b}\cdot\pi_{\theta_{t}+\Delta\theta_{t}}(s,b)\right]$
$\displaystyle=$
$\displaystyle-\mathbb{E}[\nabla\log\pi_{\theta_{t}+\Delta\theta_{t}}(s,a)].$

This ends the proof.

∎

###  A.6 Proof of Theorem 4

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

For all $i\in N$, define the following
$z^{i}_{t}=[\mu^{i}_{t},(\lambda^{i}_{t})^{\top},(v^{i}_{t})^{\top}]^{\top}\in\mathbb{R}^{1+M+L}$.
Firstly, we recall the following lemma from [Zhang et al., 2018] to give the
bounds on $z^{i}_{t}$ (for proof see [Zhang et al., 2018]).

######  Lemma 6.

Under assumptions X. 1, X. 2, and X. 3 the sequence $\\{z^{i}_{t}\\}$ satisfy
$sup_{t}~{}||z^{i}_{t}||<\infty$ a.s., for all $i\in{N}$.

Now consider the actor step as given in Equation (20)

$\displaystyle\theta^{i}_{t+1}$ $\displaystyle=$
$\displaystyle\theta^{i}_{t}+\beta_{\theta,t}\cdot
G_{t}^{i^{-1}}\cdot\tilde{\delta}^{i}_{t}\cdot\psi^{i}_{t}$ (61)
$\displaystyle=$
$\displaystyle\theta^{i}_{t}+\beta_{v,t}\cdot\frac{\beta_{\theta,t}}{\beta_{v,t}}\cdot
G_{t}^{i^{-1}}\cdot\tilde{\delta}^{i}_{t}\cdot\psi^{i}_{t}.$

By assumption, $\frac{\beta_{\theta,t}}{\beta_{v,t}}\rightarrow 0$. Also note
that $\tilde{\delta}^{i}_{t}\cdot\psi^{i}_{t}$ is bounded by assumptions and
Lemma 6. Moreover, $G_{t}^{i^{-1}}$ is bounded by assumption X. 4. Thus, the
actor update in Equation (61) can be traced via an ODE $\dot{\theta}^{i}=0$.
Hence we can fix the value of $\theta_{t}$ as constant $\theta$ while
analyzing the critic-step at the faster time scale. Note that the above
argument of taking $\theta_{t}\equiv\theta$ while analyzing the critic step is
common to all the 3 MAN algorithms. The only difference is in actor update
Equation (61), nonetheless a similar argument concludes that
$\theta_{t}\equiv\theta$.

Let
$\mathcal{F}_{t,4}=\sigma(r_{\tau},\mu_{\tau},\lambda_{\tau},v_{\tau},s_{\tau},a_{\tau},C_{\tau-1},\tau\leq
t)$ be the filtration which is an increasing $\sigma$-algebra over time $t$.
Define the following for notation convenience. Let
$r_{t}=[r^{1}_{t},\dots,r^{n}_{t}]^{\top},~{}v_{t}=[(v^{1}_{t})^{\top},\dots,(v^{n}_{t})^{\top}]^{\top},~{}\delta_{t}=[(\delta^{1}_{t})^{\top},\dots,(\delta^{n}_{t})^{\top}]^{\top}$,
and
$z_{t}=[(z^{1}_{t})^{\top},\dots,(z^{n}_{t})^{\top}]^{\top}\in\mathbb{R}^{n(1+M+L)}$.
Moreover, let $A\otimes B$ represents the Kronecker product of matrices $A$
and $B$. Let $y_{t}=[(y^{1}_{t})^{\top},\dots,(y^{n}_{t})^{\top}]^{\top}$,
where
$y^{i}_{t+1}=[r^{i}_{t+1}-\mu^{i}_{t},(r^{i}_{t+1}-f_{t}^{\top}\lambda^{i}_{t})f_{t}^{\top},\delta^{i}_{t}\varphi_{t}^{\top}]^{\top}$.
Recall, $f_{t}=f(s_{t},a_{t})$, and $\varphi_{t}=\varphi(s_{t})$. Let $I$ be
the identity matrix of the dimension $(1+M+L)\times(1+M+L)$. Then update of
$z_{t}$ can be written as

$z_{t+1}=(C_{t}\otimes I)(z_{t}+\beta_{v,t}\cdot y_{t+1}).$ (62)

Let $\mathbbm{1}=(1,\dots,1)$ represents the vector of all 1’s. We define the
operator $\left\langle z\right\rangle=\frac{1}{n}(\mathbbm{1}^{\top}\otimes
I)z=\frac{1}{n}\sum_{i\in{N}}z^{i}$. This $\langle
z\rangle\in\mathbb{R}^{1+M+L}$ represents the average of the vectors in
$\\{z^{1},z^{2},\dots,z^{n}\\}$. For notational simplicity let $k=1+M+L$.
Moreover, let $\mathcal{J}=(\frac{1}{n}\mathbbm{1}\mathbbm{1}^{\top})\otimes
I\in\mathbb{R}^{nk\times nk}$ is the projection operator that projects a
vector into the consensus subspace $\\{\mathbbm{1}\otimes
u:u\in\mathbb{R}^{k}\\}$. Thus $\mathcal{J}z=\mathbbm{1}\otimes\langle
z\rangle$. Now define the disagreement vector
$z_{\perp}=\mathcal{J}_{\perp}z=z-\mathbbm{1}\otimes\langle z\rangle$, where
$\mathcal{J}_{\perp}=I-\mathcal{J}$. Here $I$ is $nk\times nk$ dimensional
identity matrix. The iteration $z_{t}$ can be separated as the sum of a vector
in disagreement space and a vector in consensus space, i.e.,
$z_{t}=z_{\perp,t}+\mathbbm{1}\otimes\langle z_{t}\rangle$. The proof of
critic step convergence consists of two steps.

Step 01: To show $lim_{t}~{}z_{\perp,t}=0$ a.s. From Lemma 6 we have
$\mathbb{P}[sup_{t}||z_{t}||<\infty]=1$, i.e.,
$\mathbb{P}[\cup_{K\in\mathbb{Z}^{+}}~{}\\{sup_{t}||z_{t}||<K\\}]=1$. It
suffices to show that
$lim_{t}~{}z_{\perp,t}\mathbbm{1}_{\\{sup_{t}||z_{t}||<K\\}}=0$ for any
$K\in\mathbb{Z}^{+}$. Lemma B.5 in [Zhang et al., 2018] proves the boundedness
of $\mathbb{E}\left[||\beta_{v,t}^{-1}z_{\perp,t}||^{2}\right]$ over the set
$\\{sup_{t}||z_{t}||\leq K\\}$, for any $K>0$. We state the lemma here.

######  Lemma 7.

Under assumptions X. 2, and X. 3 for any $K>0$, we have

$sup_{t}~{}\mathbb{E}[||\beta_{v,t}^{-1}z_{\perp,t}||^{2}\mathbbm{1}_{\\{sup_{t}||z_{t}||\leq
K\\}}]<\infty.$

From Lemma 7 we obtain that for any $K>0,~{}\exists~{}K_{1}<\infty$ such that
for any $t\geq 0,~{}\mathbb{E}[||z_{\perp,t}||^{2}]<K_{1}\beta_{v,t}^{2}$ over
the set $\\{sup_{t}~{}||z_{t}||<K\\}$. Since $\sum_{t}\beta_{v,t}^{2}<\infty$,
by Fubini’s theorem we have
$\sum_{t}\mathbb{E}(||z_{\perp,t}||^{2}\mathbbm{1}_{\\{sup_{t}\
||z_{t}||<K\\}})<\infty$. Thus,
$\sum_{t}||z_{\perp,t}||^{2}\mathbbm{1}_{\\{sup_{t}\ ||z_{t}||<K\\}}<\infty$
a.s. Therefore,
$lim_{t}~{}z_{\perp,t}\mathbbm{1}_{\\{sup_{t}||z_{t}||<K\\}}=0$ a.s. Since
$\\{sup_{t}||z_{t}||<\infty\\}$ with probability 1, thus
$lim_{t}~{}z_{\perp,t}=0$ a.s. This ends the proof of Step 01.

Step 02: To show the convergence of the consensus vector
$\mathbbm{1}\otimes\langle z_{t}\rangle$ first, note that the iteration of
$\langle z_{t}\rangle$ (Equation (62)) can be written as

$\displaystyle\langle z_{t+1}\rangle$ $\displaystyle=$
$\displaystyle\frac{1}{N}(\mathbbm{1}^{\top}\otimes I)(C_{t}\otimes
I)(\mathbbm{1}\otimes\langle z_{t}\rangle+z_{\perp,t}+\beta_{v,t}y_{t+1})$
(63) $\displaystyle=$ $\displaystyle\langle
z_{t}\rangle+\beta_{v,t}\langle(C_{t}\otimes
I)(y_{t+1}+\beta_{v,t}^{-1}z_{\perp,t})\rangle$ $\displaystyle=$
$\displaystyle\langle z_{t}\rangle+\beta_{v,t}\mathbb{E}(\langle
y_{t+1}\rangle|\mathcal{F}_{t,4})+\beta_{v,t}\xi_{t+1},$

where

$\displaystyle\xi_{t+1}$ $\displaystyle=$ $\displaystyle\langle(C_{t}\otimes
I)(y_{t+1}+\beta_{v,t}^{-1}z_{\perp,t})\rangle-\mathbb{E}(\langle
y_{t+1}\rangle|\mathcal{F}_{t,4}),~{}~{}and$ $\displaystyle\langle
y_{t+1}\rangle$ $\displaystyle=$
$\displaystyle[\bar{r}_{t+1}-\langle\mu_{t}\rangle,(\bar{r}_{t+1}-f_{t}^{\top}\langle\lambda_{t}\rangle)f_{t}^{\top},\langle\delta_{t}\rangle\varphi_{t}^{\top}]^{\top}.$

Here
$\langle\delta_{t}\rangle=\bar{r}_{t+1}-\langle\mu_{t}\rangle+\varphi^{\top}_{t+1}\langle
v_{t}\rangle-\varphi^{\top}_{t}\langle v_{t}\rangle$. Note that
$\mathbb{E}(\langle y_{t+1}\rangle|\mathcal{F}_{t,4})$ is Lipschitz continuous
in $\langle
z_{t}\rangle=(\langle\mu_{t}\rangle,\langle\lambda_{t}\rangle^{\top},\langle
v_{t}\rangle^{\top})^{\top}$. Moreover, $\xi_{t+1}$ is a martingale difference
sequence and satisfies

$\mathbb{E}[||\xi_{t+1}||^{2}~{}|~{}\mathcal{F}_{t,4}]\leq\mathbb{E}[||y_{t+1}+\beta_{v,t}^{-1}z_{\perp,t}||^{2}_{S_{t}}~{}|~{}\mathcal{F}_{t,4}]+||\mathbb{E}(\langle
y_{t+1}\rangle~{}|~{}\mathcal{F}_{t,4})||^{2},$ (64)

where $S_{t}=\frac{C_{t}^{\top}\mathbbm{1}\mathbbm{1}^{\top}C_{t}\otimes
I}{n^{2}}$ has bounded spectral norm. Bounding first and second terms in RHS
of Equation (64) we have, for any $K>0$

$\mathbb{E}(||\xi_{t+1}||^{2}|\mathcal{F}_{t,4})\leq K_{2}(1+||\langle
z_{t}\rangle||^{2}),$

over the set $\\{sup_{t}~{}||z_{t}||\leq K\\}$ for some $K_{2}<\infty$. The
ODE associated with the Equation (63) has the form

$\langle\dot{z}\rangle=\begin{pmatrix}\langle\dot{\mu}\rangle\\\
\langle\dot{\lambda}\rangle\\\
\langle\dot{v}\rangle\end{pmatrix}=\begin{pmatrix}-1&0&0\\\
0&-F^{\top}D_{\theta}^{s,a}F&0\\\
-\Phi^{\top}D_{\theta}^{s}\mathbbm{1}&0&\Phi^{\top}D_{\theta}^{s}(P^{\theta}-I)\Phi\end{pmatrix}\begin{pmatrix}\langle\mu\rangle\\\
\langle\lambda\rangle\\\ \langle
v\rangle\end{pmatrix}+\begin{pmatrix}J(\theta)\\\
F^{\top}D_{\theta}^{s,a}\bar{R}\\\
\Phi^{\top}D_{\theta}^{s}\bar{R}_{\theta}\end{pmatrix}.$ (65)

Let the RHS of equation (65) be $h(\langle z\rangle)$. Note that $h(\langle
z\rangle)$ is Lipschitz continuous in $\langle z\rangle$. Also, recall that
$D_{\theta}^{s,a}=diag[d_{\theta}(s)\cdot\pi_{\theta}(s,a),s\in\mathcal{S},a\in\mathcal{A}]$.
Using assumption X. 1, and Perron-Frobenius theorem the stochastic matrix
$P^{\theta}$ has a eigenvalue of 1, and remaining eigenvalues have real part
less than 1. Hence $(P^{\theta}-I)$ has one eigenvalue zero, and all other
eigenvalues with negative real parts. Same follows for the matrix
$\Phi^{\top}D_{\theta}^{s}(P^{\theta}-I)\Phi$, since $\Phi$ is full rank
column matrix. The simple eigen-vector $\nu$ of the matrix satisfies
$\Phi\nu=\alpha\mathbbm{1}$ for some $\alpha\neq 0$. However, this will not
happen because of the assumption X. 3. Hence the ODE given in Equation (65)
has unique globally asymptotically stable equilibrium
$[J(\theta),\lambda_{\theta}^{\top},v_{\theta}^{\top}]^{\top}$ satisfying

$\displaystyle-\langle\mu\rangle+J(\theta)=0;~{}~{}F^{\top}D_{\theta}^{s,a}(\bar{R}-F\lambda_{\theta})=0;~{}~{}\Phi^{\top}D_{\theta}^{s}[T_{\theta}^{V}(\Phi
v_{\theta})-\Phi v_{\theta}]=0.$

Moreover, from Lemma 6, and Lemma 7, the sequence $\\{z_{t}\\}$ is bounded
almost surely, so is the sequence $\\{\langle z_{t}\rangle\\}$. Specializing
Corollary 8 and Theorem 9 on page 74-75 in [Borkar, 2009] we have
$lim_{t}~{}\langle\mu_{t}\rangle=J(\theta),~{}lim_{t}~{}\langle\lambda_{t}\rangle=\lambda_{\theta}$,
and $lim_{t}~{}\langle v_{t}\rangle=v_{\theta}$ a.s. over the set
$\\{sup_{t}~{}||z_{t}||\leq K\\}$ for any $K>0$. This concludes the proof of
Step 02.

The proof of the theorem thus follows from Lemma 6 and results from Step 01.
Thus, 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 $i\in{N}$. ∎

##  Appendix B Further details on computational experiments

This section will provide further details of the computational experiments for
traffic network control and the abstract multi-agent reinforcement learning
setup.

###  B.1 Experiments for abstract multi-agent reinforcement learning model

We will provide the details of the experiments for an abstract multi-agent RL
model we have considered in Section 5.2.

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}=\\{0,1\\}$. Therefore, 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 be stochastic. 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)$
is sampled uniformly from the interval $[0,4]$ for each agent $i\in N$, and
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

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

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$. We set $m_{i}=5,~{}\forall i\in
N$. All the elements of $q_{s,b^{i}}$ are also uniformly sampled from $[0,1]$.
For the Boltzmann policy function we have [Sutton et al., 1999]

$\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}}.$

The features for state value function $\varphi(s)\in\mathcal{R}^{L}$ are
uniformly sampled from $[0,1]$ of dimension $L=5<<|\mathcal{S}|$, whereas the
features for the reward function $f(s,a)\in\mathbb{R}^{M}$ are uniformly
sampled from $[0,1]$ of dimension $M=10<<|\mathcal{S}||\mathcal{A}|$. The
communication network $\mathcal{G}_{t}$ is generated randomly at each time
$t$, such that the links in the network are formed with the connectivity
ratio444Ratio of total degree of the graph and the degree of complete graph,
i.e., $\frac{2E}{n(n-1)}$, where $E$ is the number of edges in the graph.
$4/n$. The step sizes are taken as $\beta_{v,t}=\frac{1}{t^{0.65}}$, and
$\beta_{\theta,t}=\frac{1}{t^{0.85}}$ respectively. Initial values 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 dimension, $\forall~{}i\in{N}$. The
Fisher information matrix inverse is initialized to $G_{0}^{i^{-1}}=1.5\times
I,~{}\forall~{}i\in N$. We compared the MAAC algorithm with the multi-agent
natural actor-critic algorithms FI-MAN, AP-MAN, and FIAP-MAN. The globally
averaged reward, standard deviation and 95% confidence intervals (averaged
over 25 iterations) for all multi-agent natural actor-critic algorithms are
given in Table 6.

Algorithm | Avg Rewards | Std Dvn | Confidence interval
---|---|---|---
MAAC | 1.993280 | 0.066421 | (1.967243, 2.019316)
FI-MAN | 2.008412 | 0.055538 | (1.986642, 2.030183)
AP-MAN | 1.982451 | 0.079404 | (1.951325, 2.013576)
FIAP-MAN | 1.981089 | 0.093754 | (1.944338, 2.017839)
Table 6: Globally averaged rewards, standard deviation and 95% confidence for
all the algorithms for the abstract multi-agent RL problem. We observe that
globally averaged rewards and standard deviation are almost same for all the
algorithms with high confidence. All the values are averaged over $25$ runs.

We see that the globally averaged returns from all the algorithms are almost
close with high confidence. Since the performance of all the algorithms are
same, we have compared the relative $V$ values, defined as
$V(s;v^{i})=v^{i^{\top}}\varphi(s)$ for each agent $i\in N$ averaged over 25
runs with each run involving $12000$ iterations. These values are available in
Table 7 (maximum values in each row are bold).

Agents | Algorithms
---|---
FI-MAN | AP-MAN | FIAP-MAN | MAAC
1 | 0.099790 | -0.081895 | 0.096078 | -0.011488
2 | 0.082189 | -0.006449 | 0.030639 | 0.012191
3 | 0.055486 | -0.078218 | 0.082690 | -0.082770
4 | 0.076051 | -0.079353 | 0.012621 | 0.015753
5 | 0.083763 | -0.063922 | 0.061808 | 0.002050
6 | 0.020304 | -0.052126 | 0.108242 | -0.008364
7 | 0.056736 | -0.105311 | 0.087904 | 0.042844
8 | 0.036493 | -0.039098 | -0.004051 | 0.052373
9 | 0.101874 | -0.026014 | 0.153574 | 0.030972
10 | 0.040236 | -0.041242 | 0.045329 | 0.016195
11 | 0.024138 | -0.035986 | 0.101919 | -0.006431
12 | 0.106377 | -0.054188 | -0.018450 | 0.012857
13 | 0.058369 | -0.049010 | 0.078504 | 0.003431
14 | 0.049588 | -0.090194 | 0.056069 | -0.003832
15 | 0.090342 | -0.057247 | 0.066245 | 0.013376
Table 7: Relative $V$ values for each agent for all algorithms averaged over
25 runs. The values in bold represent the maximum in each row, i.e., for each
agent. The relative $V$ values are maximum either for FI-MAN or FIAP-MAN
algorithm for all the agents except agent $8$, suggesting that natural actor-
critic algorithms have better relative $V$ value than standard gradient-based
MAAC algorithm. However, the globally averaged returns are almost the same for
all the algorithms as shown in Table 6.

Though the globally averaged returns are almost the same for all the
algorithms, the relative $V$ values are maximum for all but agent $8$ in the
FI-MAN or FIAP-MAN algorithms showing the usefulness of multi-agent natural
actor-critic algorithms.

###  B.2 Experiments for traffic network control

Here we provide some more details about the traffic network congestion model
for both arrival patterns.

####  B.2.1 More performance details for arrival pattern 1

Though we aim to minimize the network congestion only, in Table 8, we also
provide the congestion to each traffic light for the last 200 decision epochs
(all the values are round off to 3 decimal places). Because of the
$p_{s,ap}$’s for arrival pattern 1, as expected the traffic light $T_{2}$ is
heavily congested; $T_{1},T_{4}$ are almost equally congested and $T_{3}$ is
the least congested. We also present the correction factor (CF) that is
calculated as $1.96\times\frac{std~{}dvn}{\sqrt{10}}$. It captures the 95%
confidence about the average congestion of each traffic light and the overall
network congestion.

Algos |  Decision Epochs | Congestion (Avg $\pm$ CF)
---|---|---
$T_{1}$ | $T_{2}$ | $T_{3}$ | $T_{4}$ | Network
MAAC | 1300 | 3.742 $\pm$ 0.071 | 4.344 $\pm$ 0.049 | 2.241 $\pm$ 0.012 | 3.716 $\pm$ 0.045 | 14.042 $\pm$ 0.053
1350 | 3.737 $\pm$ 0.072 | 4.345 $\pm$ 0.050 | 2.239 $\pm$ 0.011 | 3.717 $\pm$ 0.041 | 14.037 $\pm$ 0.054
1400 | 3.742 $\pm$ 0.065 | 4.344 $\pm$ 0.049 | 2.242 $\pm$ 0.011 | 3.708 $\pm$ 0.042 | 14.035 $\pm$ 0.043
1450 | 3.741 $\pm$ 0.061 | 4.347 $\pm$ 0.053 | 2.246 $\pm$ 0.011 | 3.705 $\pm$ 0.042 | 14.039 $\pm$ 0.046
1500 | 3.733 $\pm$ 0.067 | 4.336 $\pm$ 0.050 | 2.249 $\pm$ 0.013 | 3.699 $\pm$ 0.040 | 14.017 $\pm$ 0.052
FI | 1300 | 2.652 $\pm$ 0.114 | 4.515 $\pm$ 0.838 | 2.359 $\pm$ 0.159 | 2.598 $\pm$ 0.041 | 12.124 $\pm$ 0.896
1350 | 2.638 $\pm$ 0.112 | 4.516 $\pm$ 0.851 | 2.358 $\pm$ 0.159 | 2.589 $\pm$ 0.042 | 12.100 $\pm$ 0.903
1400 | 2.633 $\pm$ 0.110 | 4.514 $\pm$ 0.856 | 2.358 $\pm$ 0.160 | 2.579 $\pm$ 0.039 | 12.084 $\pm$ 0.910
1450 | 2.623 $\pm$ 0.111 | 4.515 $\pm$ 0.871 | 2.361 $\pm$ 0.161 | 2.569 $\pm$ 0.039 | 12.068 $\pm$ 0.921
1500 | 2.613 $\pm$ 0.110 | 4.492 $\pm$ 0.868 | 2.359 $\pm$ 0.161 | 2.564 $\pm$ 0.038 | 12.028 $\pm$ 0.918
AP | 1300 | 3.754 $\pm$ 0.077 | 4.349 $\pm$ 0.045 | 2.236 $\pm$ 0.013 | 3.758 $\pm$ 0.041 | 14.097 $\pm$ 0.048
1350 | 3.747 $\pm$ 0.078 | 4.346 $\pm$ 0.046 | 2.235 $\pm$ 0.011 | 3.761 $\pm$ 0.036 | 14.089 $\pm$ 0.047
1400 | 3.755 $\pm$ 0.072 | 4.345 $\pm$ 0.045 | 2.238 $\pm$ 0.011 | 3.751 $\pm$ 0.037 | 14.091 $\pm$ 0.039
1450 | 3.756 $\pm$ 0.068 | 4.348 $\pm$ 0.048 | 2.243 $\pm$ 0.011 | 3.752 $\pm$ 0.041 | 14.099 $\pm$ 0.041
1500 | 3.748 $\pm$ 0.073 | 4.338 $\pm$ 0.046 | 2.247 $\pm$ 0.013 | 3.746 $\pm$ 0.039 | 14.079 $\pm$ 0.051
FIAP | 1300 | 2.757 $\pm$ 0.245 | 3.855 $\pm$ 0.376 | 1.929 $\pm$ 0.148 | 2.939 $\pm$ 0.165 | 11.479 $\pm$ 0.691
1350 | 2.743 $\pm$ 0.236 | 3.833 $\pm$ 0.372 | 1.923 $\pm$ 0.149 | 2.926 $\pm$ 0.161 | 11.424 $\pm$ 0.680
1400 | 2.735 $\pm$ 0.229 | 3.827 $\pm$ 0.383 | 1.916 $\pm$ 0.147 | 2.910 $\pm$ 0.156 | 11.388 $\pm$ 0.675
1450 | 2.723 $\pm$ 0.222 | 3.809 $\pm$ 0.380 | 1.913 $\pm$ 0.149 | 2.897 $\pm$ 0.152 | 11.342 $\pm$ 0.662
1500 | 2.711 $\pm$ 0.214 | 3.785 $\pm$ 0.371 | 1.907 $\pm$ 0.148 | 2.883 $\pm$ 0.147 | 11.287 $\pm$ 0.645
Table 8: Table shows the average congestion $\pm$ correction factor (averaged
over 10 runs) to each traffic light and to the entire network in last 200
decision epochs for arrival pattern 1. As expected, the average congestion is
the highest for traffic light $T_{2}$ in all the algorithms, almost same for
traffic lights $T_{1},T_{4}$ and least for traffic light $T_{3}$. The overall
network congestion is simply the sum of congestion at all the traffic lights.
Moreover, for the last 200 decision epochs all the values are close to each
other with high confidence implying that the algorithms indeed are attaining
the local minima.

For completeness, we now provide the plots of norm of the differences for
agents $T_{2},T_{3},T_{4}$ in Figure 8.

Figure 8: Norm of difference of agent $T_{2},T_{3},T_{4}$ for all the
algorithms. The left panel is shown upto 350 epochs, however to show that
actor parameters are actually differing from iterate 2 itself, we zoom them in
the left figure. These observations illustrate Theorem 3 and related
discussions in Section 3.4.

####  B.2.2 More performance details of arrival pattern 2

Table 9 provides the average network congestion and the congestion to each
traffic light for last 200 decision epochs. As expected from arrival pattern
2, all the traffic lights are almost equally congested. Again CF is the
correction factor as defined earlier.

Algos |  Decision Epochs | Congestion (Avg $\pm$ CF)
---|---|---
$T_{1}$ | $T_{2}$ | $T_{3}$ | $T_{4}$ | Network
MAAC | 1300 | 3.486 $\pm$ 0.074 | 3.378 $\pm$ 0.031 | 3.348 $\pm$ 0.042 | 3.445 $\pm$ 0.037 | 13.658 $\pm$ 0.130
1350 | 3.485 $\pm$ 0.073 | 3.375 $\pm$ 0.031 | 3.361 $\pm$ 0.041 | 3.448 $\pm$ 0.035 | 13.670 $\pm$ 0.130
1400 | 3.482 $\pm$ 0.071 | 3.373 $\pm$ 0.034 | 3.355 $\pm$ 0.040 | 3.448 $\pm$ 0.033 | 13.656 $\pm$ 0.129
1450 | 3.489 $\pm$ 0.073 | 3.381 $\pm$ 0.035 | 3.350 $\pm$ 0.034 | 3.442 $\pm$ 0.036 | 13.662 $\pm$ 0.130
1500 | 3.481 $\pm$ 0.070 | 3.379 $\pm$ 0.034 | 3.348 $\pm$ 0.032 | 3.438 $\pm$ 0.033 | 13.646 $\pm$ 0.122
FI | 1300 | 2.560 $\pm$ 0.048 | 2.554 $\pm$ 0.041 | 2.541 $\pm$ 0.046 | 2.609 $\pm$ 0.052 | 10.264 $\pm$ 0.087
1350 | 2.554 $\pm$ 0.047 | 2.547 $\pm$ 0.044 | 2.539 $\pm$ 0.045 | 2.605 $\pm$ 0.048 | 10.244 $\pm$ 0.083
1400 | 2.545 $\pm$ 0.047 | 2.540 $\pm$ 0.043 | 2.534 $\pm$ 0.044 | 2.599 $\pm$ 0.047 | 10.217 $\pm$ 0.079
1450 | 2.541 $\pm$ 0.046 | 2.535 $\pm$ 0.040 | 2.524 $\pm$ 0.044 | 2.593 $\pm$ 0.045 | 10.194 $\pm$ 0.073
1500 | 2.532 $\pm$ 0.047 | 2.530 $\pm$ 0.040 | 2.519 $\pm$ 0.045 | 2.589 $\pm$ 0.045 | 10.170$\pm$ 0.074
AP | 1300 | 3.515 $\pm$ 0.070 | 3.400 $\pm$ 0.026 | 3.377 $\pm$ 0.046 | 3.488 $\pm$ 0.037 | 13.780 $\pm$ 0.129
1350 | 3.514 $\pm$ 0.067 | 3.398 $\pm$ 0.028 | 3.388 $\pm$ 0.045 | 3.490 $\pm$ 0.031 | 13.792 $\pm$ 0.126
1400 | 3.513 $\pm$ 0.064 | 3.397 $\pm$ 0.032 | 3.383 $\pm$ 0.043 | 3.490 $\pm$ 0.029 | 13.783 $\pm$ 0.123
1450 | 3.518 $\pm$ 0.066 | 3.407 $\pm$ 0.033 | 3.377 $\pm$ 0.037 | 3.488 $\pm$ 0.035 | 13.790 $\pm$ 0.126
1500 | 3.511 $\pm$ 0.064 | 3.404 $\pm$ 0.032 | 3.376 $\pm$ 0.034 | 3.485 $\pm$ 0.033 | 13.776 $\pm$ 0.117
FIAP | 1300 | 2.591 $\pm$ 0.043 | 2.558 $\pm$ 0.037 | 2.570 $\pm$ 0.043 | 2.579 $\pm$ 0.038 | 10.298 $\pm$ 0.140
1350 | 2.586 $\pm$ 0.042 | 2.549 $\pm$ 0.036 | 2.564 $\pm$ 0.043 | 2.576 $\pm$ 0.034 | 10.275 $\pm$ 0.134
1400 | 2.577 $\pm$ 0.042 | 2.544 $\pm$ 0.035 | 2.557 $\pm$ 0.041 | 2.569 $\pm$ 0.035 | 10.247 $\pm$ 0.135
1450 | 2.574 $\pm$ 0.039 | 2.540 $\pm$ 0.034 | 2.549 $\pm$ 0.041 | 2.562 $\pm$ 0.034 | 10.226 $\pm$ 0.128
1500 | 2.566 $\pm$ 0.041 | 2.534 $\pm$ 0.034 | 2.543 $\pm$ 0.041 | 2.556 $\pm$ 0.036 | 10.199 $\pm$ 0.132
Table 9: Table shows the average congestion $\pm$ correction factor (averaged
over 10 runs) to each traffic light and to the entire network in last 200
decision epochs for arrival pattern 2. As expected, the average congestion is
almost the same for all traffic lights in all the algorithms.

We again plot the norm of the difference of the actor parameter for remaining
agent $T_{2},T_{3}$ and $T_{4}$ in Figure 9 .

Figure 9: For arrival pattern 2, norm of difference of agent
$T_{2},T_{3},T_{4}$ for all the algorithms. The left panel is shown upto 350
epochs, however to show that actor parameters are actually differing from
iterate 2 itself, we zoom them in the left figure. These observations
illustrate Theorem 3 in Section 3.4.

####  B.2.3 Justification of Equation (53)

We first use the law of total probability to show that for a given arrival
pattern $ap$ the number of arrivals to the source node $s$ at time $t$ follows
the binomial distribution as given in Equation (53).

$\displaystyle\mathbb{P}(N_{t}^{s}=k|M_{t}=ap)$
$\displaystyle=\sum_{j=0}^{N_{v}}\mathbb{P}(N_{t}^{s}=k|N_{t}=j,M_{t}=ap)\mathbb{P}(N_{t}=j|M_{t}=ap)$
$\displaystyle=\sum_{j=k}^{N_{v}}\binom{j}{k}p_{s,ap}^{k}(1-p_{s,ap})^{j-k}\mathbb{P}(N_{t}=j)$
$\displaystyle=p_{s,ap}^{k}\sum_{j=0}^{N_{v}}\binom{j}{k}\binom{N_{v}}{j}(1-p_{s,ap})^{j-k}\left(\frac{1}{T}\right)^{j}\left(1-\frac{1}{T}\right)^{N_{v}-j}$
$\displaystyle=\binom{N_{v}}{k}p_{s,ap}^{k}\sum_{l=0}^{N_{v}-k}\binom{N_{v}-k}{l}(1-p_{s,ap})^{N_{v}-k-l}\left(\frac{1}{T}\right)^{N_{v}-l}\left(1-\frac{1}{T}\right)^{l}$
$\displaystyle=\binom{N_{v}}{k}\left(\frac{p_{s,ap}}{T}\right)^{k}\left(1-\frac{p_{s,ap}}{T}\right)^{N_{v}-k}.$

##  Appendix C Some relevant background

In this section, we will provide details of single-agent MDP, actor-critic
algorithm, the MAAC algorithm [Zhang et al., 2018], and the Kushner-Clark
Lemma.

###  C.1 Markov decision processes and actor-critic algorithms with linear
function approximation

Markov decision process (MDP) is a stochastic control process that provides a
mathematical framework for sequential decision making. Formally it is defined
as below.

######  Definition 1 (MDP [Puterman, 2014]).

A MDP is characterised by a quadruple
$\mathcal{M}=\langle\mathcal{S,A},P,r\rangle$, where $\mathcal{S}$ and
$\mathcal{A}$ are finite state and action space respectively.
${P}:\mathcal{S}\times\mathcal{A}\times\mathcal{S}\rightarrow[0,1]$ is the
transition probability of taking action $a$ in state $s$ and reaching to state
$s^{\prime}$. ${R}$ : $\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R}$ is
the reward function defined as ${R}(s,a)=\mathbb{E}[r_{t+1}|s_{t}=s,a_{t}=a]$
where $r_{t+1}$ is the instantaneous reward at time $t$.

The policy of an agent is a decision rule using which agent takes action in
each state; formally, it is a mapping
$\pi:\mathcal{S}\times\mathcal{A}\rightarrow[0,1]$. It also represents the
probability of taking action $a$ in the state $s$. The goal of the agent is to
maximize the expected average reward,

$\max_{\pi}~{}~{}J(\pi)=\max_{\pi}~{}~{}\underset{T}{lim}\hskip
2.0pt\dfrac{1}{T}\sum_{t=0}^{T-1}\mathbb{E}(r_{t+1})=\max_{\pi}~{}~{}\sum_{s\in\mathcal{S}}d_{\pi}(s)\sum_{a\in\mathcal{A}}\pi(s,a){R}(s,a),$

where $d_{\pi}(s)=\underset{t}{lim}~{}\mathbb{P}(s_{t}=s|\pi)$ is the
stationary state distribution of the Markov chain under policy $\pi$. The
action value function for a policy, $\pi(\cdot,\cdot)$ is defined as

$Q_{\pi}(s,a)=\sum_{t\geq 0}\mathbb{E}[r_{t+1}-J(\pi)|s_{0}=s,a_{0}=a,\pi].$

The state value function $V_{\pi}(s)$ for any state $s$ is defined as

${V}_{\pi}(s)=\sum_{a\in\mathcal{A}}\pi(s,a){Q}_{\pi}(s,a).$

In most real-life scenarios, the state space, the action space, or both are
large and infinite, and hence finding the optimal policy is computationally
heavy so, it is useful to consider the parameterized policies. Let the
parameterized policy be denoted by $\pi_{\theta}$. We need the following
regularity assumption on the parameterized policy function [Bhatnagar et al.,
2009a, Sutton and Barto, 2018]. For any $s\in\mathcal{S}$, and
$a\in\mathcal{A}$, the policy function $\pi_{\theta}(s,a)>0$ for any
$\theta\in\Theta$. Also, $\pi_{\theta}(s,a)$ is continuously differentiable
with respect to the parameter $\theta$ over $\Theta$. Moreover, for any
$\theta\in\Theta$, let $P^{\theta}$ be 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).$

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

Under this parameterization, the policy gradient theorem [Sutton and Barto,
2018] is: $\nabla_{\theta}J(\theta)=\mathbb{E}_{s\sim
d_{\theta},a\sim\pi_{\theta}}[\nabla_{\theta}\hskip 2.0ptlog\hskip
2.0pt\pi_{\theta}(s,a)\cdot\\{Q_{\theta}(s,a)-b(s)\\}]$. The term $b(s)$ is
usually referred to as the baseline. This baseline helps in reducing the
variance in the gradient of the objective function. It turns out that
${V}_{\theta}$(s) serves as the minimum variance baseline. We define the
advantage function as follows:
$A_{\theta}(s,a)={Q}_{\theta}(s,a)-{V}_{\theta}(s)$.

The actor-critic algorithm is obtained by parameterizing the state value
function. Let the state value function, $V_{\theta}(s)$ be parameterized as
$V_{t+1}(v_{t}):=v_{t}^{\top}\varphi(s_{t+1})$, where $v_{t}$ are the
parameters and $\varphi(s_{t+1})$ are the features associated to the state
$s_{t+1}$. Moreover, let $\mu_{t}$ be the estimate of the objective function
at time $t$. The actor-critic algorithms use the following to update the
critic and actor parameters

$\displaystyle\textbf{Critic update:}\hskip 11.38109pt\mu_{t+1}$
$\displaystyle=(1-\beta_{v,t})\cdot\mu_{t}+\beta_{v,t}\cdot r_{t+1};\hskip
8.53581ptv_{t+1}=v_{t}+\beta_{v,t}\cdot\delta_{t}\cdot\nabla_{v}{V}_{t}(v_{t})$
$\displaystyle\textbf{Actor update:}\hskip 11.38109pt\theta_{t+1}$
$\displaystyle=\theta_{t}+\beta_{\theta,t}\cdot\delta_{t}\cdot\psi_{t},$

where $\delta_{t}$ is the TD error involving the state value function and
defined as $\delta_{t}=r_{t+1}-\mu_{t}+{V}_{t+1}(v_{t})-{V}_{t}(v_{t})$. It is
known to be an unbiased estimate of the advantage function [Bhatnagar et al.,
2009a], i.e.,
$\mathbb{E}[\delta_{t}|s_{t}=s,a_{t}=s,\pi_{\theta}]=A_{\theta}(s,a)$. Here
$\beta_{\theta,t}$ and $\beta_{v,t}$ are step-sizes and satisfy the following
conditions

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

moreover, $\beta_{\theta,t}=o(\beta_{v,t})$, and
$lim_{t}\frac{\beta_{v,t+1}}{\beta_{v,t}}=1$.

###  C.2 Taylor’s formula with Lagrange’s form of remainder in several
variables [Folland, 1999]

Let $f:\mathbb{R}^{k}\mapsto\mathbb{R}$ be a continuously double
differentiable function and $S$ be an open convex set in $\mathbb{R}^{k}$.
Then for any $\mathbf{a},\mathbf{h}\in S$, the first order Taylor expansion of
$f(\mathbf{a}+\mathbf{h})$ with Lagrange form of remainder is [Folland, 1999]

$f(\mathbf{a}+\mathbf{h})=f(\mathbf{a})+\mathbf{a}^{\top}\nabla
f(\mathbf{a})+R_{1}(\mathbf{h})$ (67)

where $R_{1}(\mathbf{h})$ is the Lagrange remainder given by

$R_{1}(\mathbf{h})=\frac{1}{2!}\mathbf{a}^{\top}\nabla^{2}f(\mathbf{a}+c\cdot\mathbf{h})\mathbf{a}~{}for~{}some~{}c\in(0,1).$
(68)

Moreover, for the above Taylor expansion we have: If each entry of the
Hessian, $\nabla^{2}f(\mathbf{a})$ is uniformly bounded by $H$, i.e.,
$|\\{\nabla^{2}f(\mathbf{a})\\}_{i,j}|\leq M,~{}\forall~{}i,j\in[k]$, then

$|R_{1}(\mathbf{h})|\leq\frac{H}{2!}||\mathbf{h}||^{2}_{1},~{}where~{}||\mathbf{h}||_{1}=|h_{1}|+|h_{2}|+\dots+|h_{n}|.$
(69)

Next, we provide the Kushner-Clark lemma that we often use while proving the
convergence.

###  C.3 Kushner-Clark Lemma [Kushner and Yin, 2003, Metivier and Priouret,
1984]

Let $\mathcal{X}\subseteq\mathbb{R}^{p}$ be a compact set and let
$h:\mathcal{X}\rightarrow\mathbb{R}^{p}$ be a continuous function. Consider
the following recursion in $p$-dimensions

$x_{t+1}=\Gamma\\{x_{t}+\gamma_{t}[h(x_{t})+\zeta_{t}+\beta_{t}]\\}.$ (70)

Let $\hat{\Gamma}(\cdot)$ be transformed projection operator defined for any
$x\in\mathcal{X}\subseteq\mathbb{R}^{p}$ as

$\hat{\Gamma}(h(x))=lim_{0<\eta\rightarrow 0}\left\\{\frac{\Gamma(x+\eta
h(x))-x}{\eta}\right\\},$

then the ODE associated with Equation (70) is $\dot{x}=\hat{\Gamma}(h(x))$.

######  X. 6.

Kushner-Clark lemma requires following assumptions

  1. 1.

Stepsize $\\{\gamma_{t}\\}_{t\geq 0}$ satisfy $\sum_{t}\gamma_{t}=\infty$, and
$\gamma_{t}\rightarrow 0$ as $t\rightarrow\infty$.

  2. 2.

The sequence $\\{\beta_{t}\\}_{t\geq 0}$ is a bounded random sequence with
$\beta_{t}\rightarrow 0$ almost surely as $t\rightarrow\infty$.

  3. 3.

For any $\epsilon>0$, the sequence $\\{\zeta_{t}\\}_{t\geq 0}$ satisfy

$\lim_{t}~{}\mathbb{P}\left(sup_{p\geq
t}\left\|\sum_{\tau=t}^{p}\gamma_{\tau}\zeta_{\tau}\right\|\geq\epsilon\right)=0.$

Kushner-Clark lemma is as follows: suppose that ODE
$\dot{x}=\hat{\Gamma}(h(x))$ has a compact set $\mathcal{K}^{\star}$ as its
asymptotically stable equilibria, then under assumption X. 6, $x_{t}$ in
Equation (70) converges almost surely to $\mathcal{K}^{\star}$ as
$t\rightarrow\infty$.

###  C.4 Multi-agent actor-critic algorithm based on state value function

For completeness, we reproduce the multi-agent actor-critic (MAAC) algorithm
based on the state value function [Zhang et al., 2018].

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},~{}\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\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}$.

Update: $t\leftarrow t+1$.

until  _Convergence_ ;

MAAC 4 Multi-agent actor-critic based on state value function