In this section, we propose a fully distributed zeroth-orther policy optimization algorithm for MARL that employs the residual-feedback zeroth-order policy gradient estimator~\eqref{eqn:Residual}. 
Specifically, we first introduce a consensus step so that the global value $J(\theta_k + \delta u_k, \xi_k)$ in the estimator \eqref{eqn:Residual} can be computed locally. Given a finite number of consensus iterations, the local estimates of $J(\theta_k + \delta u_k, \xi_k)$ will be inexact and, therefore, the local policy gradient estimates will be biased. 
To control this bias, we then introduce a value tracking technique that reduces the bias at the current episode using the local estimates of $J(\theta_k+\delta u_k, \xi_k)$ from previous episodes. Finally, we provide convergence results showing that the proposed distributed zeroth-ortder policy optimization method with constant stepsize converges to a neighborhood of the global optimal policy that is controlled by the number of consensus steps during each episode. Proofs of all theoretical results that follow can be found in the supplementary materials.

Our proposed algorithm is summarized in Algorithm~\ref{alg:DZO}. 

In what follows, we also assume that the $N$ agents form a communication graph $\mathcal{G} = (\mathcal{V}, \mathcal{E})$, where $\mathcal{V} = \{1, 2, \dots, N\}$ is the index set of agents and $\mathcal{E}$ represents the set of edges. The edge $(i,j) \in \mathcal{E}$ if agents $i$ and $j \in \mathcal{N}$ can directly send information to each other. Moreover, we define by $W \in \mathbb{R}^{N \times N}$ a weight matrix associated with the graph $\mathcal{G}$ such that the entry $W_{ij} > 0$ when $(i,j) \in \mathcal{E}$ and $W_{ij} = 0$ otherwise. 

Note that the communication graph $\mathcal{G}$ is independent of the coupling between agents in their state transition function $\mathcal{P}(s_t, a_t, s_{t+1})$ and reward functions $\{r_i(s_t, a_t)\}$ defined in Section~\ref{sec:MARL}.

\begin{algorithm}[t]
	\small
	\SetAlgoLined
	\KwIn{Exploration parameter $\delta$, stepsize $\alpha$, consensus matrix $W$, number of consenseus steps $N_c$, initial policy parameter $\theta_0$, discount ratio $\gamma$, maximum number of time steps run per episode $t_{\max}$, number of episodes $K$, and the logic variable $\mathtt{DoTracking}$.}
	Set $\mu_i^{-1}(N_c) = 0$ for all $i = 1, 2, \dots, N$ \;
	\For{episode $k = 0, 1, 2, \dots, K$}{
		For agents $i = 1, 2, \dots, N$, let agent $i$ sample a random exploration direction $u_{i,k}$ from the standard multivariate normal distribution \;
		
		Let all agents implement their perturbed policy $\pi_i(\theta_{i,k} + \delta u_{i,k})$ for $t_{\max}$ time steps and construct unbiased estimates of their local accumulated rewards $\{ J_i(\theta_k + \delta u_k, \xi_k)\}$ \;
		
		For all agent $i = 1, 2, \dots, N$, \\
		\eIf{$\mathtt{DoTracking} = \mathtt{False} \; \mathbf{ or } \; k == 0$}
		{set $\mu_i^k(0) = J_i(\theta_k + \delta u_k, \xi_k)$ \;}{
			set $\mu_i^k(0) = \mu_i^{k-1}(N_c) + J_i(\theta_k + \delta u_k, \xi_k) - J_i(\theta_{k-1} + \delta u_{k-1}, \xi_{k-1})$ \;}
		
		\For{$m = 0, 2, \dots, N_c-1$}{
			For agents $i = 1, 2, \dots, N$, let agent $i$ send $\mu_i^k(m)$ to its direct neighbors $j \in \mathcal{N}_i$ and conduct local averaging by computing $\mu_i^k(m+1) = \sum_{j \in \mathcal{N}_i} W_{ij} \mu_j^k(m)$ \;


		}
		For agents $i = 1, 2, \dots, N$, let agent $i$ update its current policy parameter $\theta_{i, k}$ by
		\begin{align}
		\label{eqn:Alg_Residual}
		& \theta_{i,k+1} = \theta_{i,k} + \alpha  \frac{\mu_i^k(N_c) - \mu_i^{k-1}(N_c)}{\delta} u_{i,k}. & 
		\end{align} 
	}
	\caption{Distributed Residual-Feedback Zeroth-Order Policy Optimization}
	\label{alg:DZO}
\end{algorithm}


\setlength{\textfloatsep}{8pt}

\subsection{Distributed Residual-Feedback Zeroth-Order Policy Optimization}
\label{sec:DZO}

In this section, we describe and analyze our proposed residual-feedback zeroth-order policy optimization algorithm in the absence of value tracking, i.e., when $\mathtt{DoTracking} = \mathtt{False}$ in Algorithm~\ref{alg:DZO} (line 6).
Specifically, at the beginning of episode $k$, the agents randomly perturb their current policy parameters $\theta_{k}$ using a random exploration direction $u_k$ and conduct on-policy local policy evaluation to obtain an unbiased estimate of the local accumulated rewards $\{ J_i(\theta_k + \delta u_k) \}_{i = 1 ,2, \dots, N}$ (lines 3-4). To conduct local policy evaluations, existing MARL methods \cite{zhang2018fullyICML,ZhangCDC2019_DistributedRL} usually assume that the global state-action pairs $(s_t, a_t)$ are available to all local agents. Under this assumption, it is possible to update the local Critic functions $Q_i^\pi(s_t, a_t)$ in \cite{zhang2018fullyICML,ZhangCDC2019_DistributedRL} to reduce the variance of policy evaluations and, therefore, the variance of the policy gradient estimates \cite{konda2000actor}. However, when the agents only have access to local observations $o_{i,t}$ which contain partial entries of $(s_t, a_t)$, these methods cannot be used. Therefore, in this paper, evaluate the local policies as $J_i(\theta_k + \delta u_k, \xi_k) = r_i(1) + \gamma r_i(2) + \gamma^2 r_i(3) + \dots$,


same as in REINFORCE \cite{williams1992simple}. This policy evaluation method can be implemented in a fully decentralized way but is subject to large variance, which increases the variance of the zeroth-order policy gradient estimates and degrades the converegence speed of the algorithm. 
The residual-feedback policy gradient estimator~\eqref{eqn:Residual} can effectively reduce this variance as we will discuss later.
In what follows, we make the following assumption on the local policy value estimator.
\begin{assumption}
	\label{asm:UnbiasedEval}
	For all agents, the local policy evaluation is unbiased and subject to bounded variance. That is, $\mathbb{E}_\xi \big[ J_i(\theta, \xi) \big] = J_i(\theta) $, and $\mathbb{E}\big[ ( J_i(\theta, \xi) - J_i(\theta) )^2 \big] \leq \sigma^2$ for $i = 1, 2, \dots, N$.
\end{assumption}

After all agents compute unbiased local policy values $J_i(\theta_{i, k}, \xi_k, \xi_k)$, they conduct $N_c$ rounds of local averaging on their local policy values $\{ J_i(\theta_k + \delta u_k, \xi_k) \}_{i = 1 ,2, \dots, N}$ (lines 7, 11-13). As a result, they obtain inexact estimates $\mu_i^k(N_c+1)$ of the global accumulated rewards $J(\theta_k + \delta u_k, \xi_k)$. To bound this estimation error, we need the following two assumptions.
\begin{assumption}
	\label{asm:Graph}
	The undirected communication graph $\mathcal{G}$ is connected and fixed for all episodes. In addition, the associated weight matrix $W$ is doubly stochastic. That is, $W \mathbf{1} = \mathbf{1} $ and $W^T \mathbf{1}  = \mathbf{1} $.
\end{assumption}
\begin{assumption}
	\label{asm:BoundVal}
	The local values $J_i(\theta, \xi)$ are upper bounded by $J_u$ and lower bounded by $J_l$ for all $i = 1, 2, \dots, N$ and all policy parameters $\theta$.
\end{assumption}
Assumption~\ref{asm:BoundVal} can be easily satisfied when the rewards are bounded and the discount factor $\gamma < 1$. When the rewards are unbounded, Assumption~\ref{asm:BoundVal} holds when all policy iterates are stabilizing policies \cite{fazel2018global}. 

Let $\mu^k(m) = [\mu_1^k(m), \dots, \mu_N^k(m)]^T$. Then, we can show the following lemma.
\begin{lemma}
	\label{lem:ConsensusErr_1}
	Given Assumptions~\ref{asm:Graph} and \ref{asm:BoundVal}, we have that $\|\mu^k(N_c) - J(\theta_{k} + \delta u_k, \xi_k) \mathbf{1}\| \leq \rho_W^{N_c} \sqrt{N} (J_u - J_l)$, where $\rho_W = \|W - \frac{1}{N}\mathbf{1}\mathbf{1}^T\| < 1$. 
\end{lemma}
Lemma~\ref{lem:ConsensusErr_1} shows that the bias in the local estimate $\mu^k(N_c)$ can be controlled by choosing a large enough $N_c$, when the local policy values are upper and lower bounded by $J_u$ and $J_l$. Using the estimates $\mu^k(N_c)$, the agents can then construct the decentralized policy gradients~\eqref{eqn:Alg_Residual} and update their policy parameters $\theta_{i,k}$ (line 14). This completes episode $k$.
The decentralized residual-feedback estimator \eqref{eqn:Alg_Residual} can reduce the variance of the policy gradient estimates, since the value estimate of the last policy iterate $\mu_i^{k-1}(N_c)$ can provide a baseline to compare $\mu_i^k(N_c)$ to.
Effectively, the value estimate of the last policy iterate has an analogous variance reduction effect to the state value $V^\pi(s)$ that is used as a baseline for the action value $Q^\pi(s, a)$ in Actor-Critic methods \cite{konda2000actor}. 
\footnote[3]{Note that the fact that the value of past policy iterates can also be used as a baseline to reduce the variance of policy gradient estimates may be of interest in its own right in the development of policy gradient methods.}
Next, we show how to select $N_c$ so that the optimality criterion~\eqref{eqn:Criterion} is satisfied.

\begin{theorem}
	\label{thm:DZO}
	{\bf (Learning Rate of Algorithm~\ref{alg:DZO} without Value Tracking)} Let Assumptions~\ref{asm:Lipschitz}, \ref{asm:UnbiasedEval}, \ref{asm:Graph} and \ref{asm:BoundVal} hold and define $\delta = \frac{\epsilon_J}{\sqrt{d}L_0}$, $  \alpha = \frac{\epsilon_J^{1.5}} {4d^{1.5}L_0^2\sqrt{K}}$, and $N_c \geq \log( \frac{\sqrt{\epsilon} \epsilon_J} { \sqrt{2} d^{1.5} L_0 (J_u - J_l))} ) / \log(\rho_W)$.


	Then, running Algorithm~\ref{alg:DZO} with $\mathtt{DoTracking} = \mathtt{False}$, we have that $\frac{1}{K} \sum_{k = 1}^{K-1} \mathbb{E}[ \| \nabla J_\delta(\theta_k) \|^2 ] \leq \mathcal{O}( d^{1.5} \epsilon_J^{-1.5} K^{-0.5} ) + \frac{\epsilon}{2}$.


\end{theorem}
As shown in Theorem~\ref{thm:DZO}, Algorithm~\ref{alg:DZO} converges to a neighborhood of the global optimal policy whose size at steady-state is equal to $\frac{\epsilon}{2}$ and can be controlled by choosing the number of consensus steps $N_c$. Moreover, the number of consensus steps $N_c$ depends not only on the user-specified accuracy level $\epsilon$ and $\epsilon_J$, but also on the range of the policy bounds $J_u$ and $J_l$. This is because the consensus iteration at each episode is independent of those at previous episodes. 
Therefore, to select $N_c$ to control the estimation bias $| \mu_i^k(N_c) - J(\theta_k + \delta u_k, \xi_k) |$, we need to select the term $J_u-J_l$ in the definition of $N_c$ in Theorem~\ref{thm:DZO} as the difference between the initial estimates $\mu_i^k(0) = J_i(\theta_k + \delta u_k, \xi_k) \in [J_l, J_u]$ that have the maximum and minimum value.

\subsection{Distributed Residual-Feedback Zeroth-Order Policy Optimization with Value Tracking}
\label{sec:DZO_ValueTracking}

As discussed before, the estimation bias $|\mu_i^k(N_c)-J(\theta_k+\delta u_k, \xi_k)|$ at episode $k$ can be reduced using local policy estimates form previous episodes. 

Specifically, rather than resetting $\mu_i^k(0) = J_i(\theta_k + \delta u_k, \xi_k)$ in line 7 of Algorithm~\ref{alg:DZO}, we update it using the estimate $\mu_i^{k-1}(N_c)$ from the last episode as $\mu_i^k(0) = \mu_i^{k-1}(N_c) + J_i(\theta_k + \delta u_k, \xi_k) - J_i(\theta_{k-1} + \delta u_{k-1}, \xi_{k-1})$.


Then, we run $N_c$ consensus iterations on $\mu_i^k(0)$ as before. Let $\bar{\mu}^k(m) = \frac{1}{N} \sum_{i = 1}^{N} \mu_i^k(m)$. The following lemma shows that the value tracking updates preserve the global information $J(\theta_{k} + \delta u_k, \xi_k)$.
\begin{lemma}
	\label{lem:AvgMu}
	Let Assumption~\ref{asm:Graph} hold. Then, running Algorithm~\ref{alg:DZO} with $\mathtt{DoTracking} = \mathtt{True}$, we have that $\bar{\mu}^k(m) = J(\theta_{k} + \delta u_k, \xi_k) = \frac{1}{N}\sum_{i = 1}^{N} J_i(\theta_{i, k}, \xi_k)$, for all $m = 1, 2, \dots, N_c$ and all $k$.
\end{lemma}
Lemma~\ref{lem:AvgMu} implies that the local estimation bias $|\mu_i^k(N_c) - J(\theta_{k} + \delta u_k, \xi_k) |$ is equal to the consensus error $|\mu_i^k(N_c) - \bar{\mu}^k(N_c)|$. Using value tracking, the bias at episode $k$ can be controlled by the consensus steps of past episodes. This is formally shown in the following lemma. 
\begin{lemma}
	\label{lem:ConsensusErr_2}
	Let Assumptions~\ref{asm:Lipschitz}, \ref{asm:UnbiasedEval}, \ref{asm:Graph} hold and define  $E_\mu^k = \|\mu_k(N_c) - \bar{\mu}_k(N_c)\|$. Then, running Algorithm~\ref{alg:DZO} with $\mathtt{DoTracking} = \mathtt{True}$, we have that


\begin{align}
\mathbb{E}\big[ (E_\mu^k)^2 \big] \leq & \bigg( 2\mathbb{E}\big[ (E_\mu^{k-1})^2 \big] + 32dL_0^2\frac{\alpha^2}{\delta^2}\mathbb{E}\big[ (E_\mu^{k-1})^2 \|u_{k-1}\|^2 \big] + 32d^2L_0^2\frac{\alpha^2}{\delta^2} \mathbb{E}\big[ (E_\mu^{k-2})^2 \big] \bigg) \rho_W^{2N_c} & \nonumber \\
& + 16NL_0^2 \alpha^2 \mathbb{E}\big[ \| \tilde{\nabla} J(\theta_{k-1})\|^2 \big] \rho_W^{2N_c} + 32Nd L_0^2 \delta^2 \rho_W^{2N_c} + 16N\sigma^2 \rho_W^{2N_c} . &
\end{align}
\end{lemma}
Compared to Lemma~\ref{lem:ConsensusErr_1}, the proposed value tracking technique makes it possible to bound the consensus error at episode $k$ with the consensus errors from episodes $k-1$ and $k-2$.  Furthermore, at each episode, this error is perturbed by the second order momentum of the policy gradient estimate~\eqref{eqn:Residual} which can be controlled by choosing a small stepsize $\alpha$ and a large number $N_c$. To see the benefit of this result, when the consensus errors from episodes $k-1$ and $k-2$ are small, value tracking needs fewer consensus iterations to achieve small consensus error at episode $k$. This is in contrast to the case without value tracking, where $N_c$ is selected regardless of previous consensus errors. The following result shows convergence of Algorithm~\ref{alg:DZO} using value tracking.
\begin{theorem}
	\label{thm:DZO_ValueTrack}
	{\bf (Learning Rate of Algorithm~\ref{alg:DZO} with Value Tracking)}


Let Assumptions~\ref{asm:Lipschitz},\ref{asm:UnbiasedEval}, \ref{asm:Graph} hold and define	$\delta = \frac{\epsilon_J}{\sqrt{d}L_0}$, $ \alpha = \frac{\epsilon_J^{1.5}} {4d^{1.5}L_0^2\sqrt{K}}$, and $N_c \geq \max\big(\log(\frac{1}{2\sqrt{2}})/\log(\rho_W)$, $\log(\sqrt{ \frac{\epsilon}{ 2G^2 \epsilon_J + 64 (d+4)^2d L_0^2  + 32d^3L_0^2\sigma^2/\epsilon_J^2}}) / \log(\rho_W) \big)$
where $G^2 = \max \bigg( \mathbb{E}\big[ \| \tilde{\nabla} J(\theta_0) \|^2\big], \frac{2 \epsilon_J \epsilon }{d K} + 32L_0^2(d+4)^2$ $+ 16d^2L_0^2 \frac{\sigma^2}{\epsilon_J^2} \bigg)$. Then, running Algorithm~\ref{alg:DZO} with $\mathtt{DoTracking} = \mathtt{True}$, we have that $\frac{1}{K} \sum_{k = 1}^{K-1} \mathbb{E}[ \| \nabla J_\delta(\theta_k) \|^2 ] \leq \mathcal{O}( d^{1.5} \epsilon_J^{-1.5} K^{-0.5} ) + \frac{\epsilon}{2}$.
\end{theorem}
In Theorem~\ref{thm:DZO_ValueTrack}, the constant $G^2$ represents the uniform bound on $\mathbb{E}[ \|\tilde{\nabla} J(\theta_{k})\|^2 ]$ for all $k = 1, 2, \dots, K$. 
Moreover, from the bounds on $N_c$ in Theorems~\ref{thm:DZO} and \ref{thm:DZO_ValueTrack}, when $\epsilon$ and $\epsilon_J$ are close to $0$, we obtain that $N_c \sim \mathcal{O}\big(\log( \frac{\sqrt{\epsilon} \epsilon_J}{d^{1.5} \sigma} ) / \log(\rho_W) \big)$ in Theorem~\ref{thm:DZO_ValueTrack} and $N_c \sim \mathcal{O}\big(\log( \frac{\sqrt{\epsilon} \epsilon_J }{d^{1.5} (J_u - J_l)} ) / \log(\rho_W) \big)$ in Theorem~\ref{alg:DZO}.
This suggests that the choice of $N_c$ in Theorem~\eqref{thm:DZO_ValueTrack} depends on the variance of function evaluation $\sigma^2$, while in Theorem~\ref{thm:DZO} the choice of $N_c$ depends on the range of value functions $[J_l, J_u]$. In practice, the variance of function evaluation $\sigma^2$ can be much smaller than the range of its value $[J_l, J_u]$. Therefore, Algorithm~\ref{alg:DZO} with value tracking requires fewer consensus steps per episode than without value tracking.


\vspace{-2mm}
{"config": "arxiv", "file": "2006.10822/tex/algorithm.tex"}