4.1 Primal-dual derivation of actor-critic methods

Throughout this subsection, we assume finite state-action sets for the sake of simplicity. Hence, the single-task objective (1) can be expressed as a dot product:

(9) \begin{eqnarray} J_{\theta}(\pi)&=& \mu^\top v^\pi_{\theta},\end{eqnarray}

where $ v^{\pi}_{\theta}\triangleq \left( v^{\pi}_{\theta}(s) \right)_{s \in \mathbb{S}}\in\mathbb{R}^{|\mathbb{S}|}$ , is a vector with the value function for every state.

We can find the maximum of (9) as the solution to the following linear programme (LP) (Puterman, Reference Puterman2005, Section 9.1):

(10) \begin{eqnarray}\begin{aligned}\underset{v}{\text{minimise}} &\;\; \mu^\top v\\\text{s.t.} \quad\;\; & v(s) \ge \sum_{s^{\prime} \in \mathbb{S}} \mathcal{P}_{\theta} (s^{\prime}|s,a) \left( r(s,a,s^{\prime}) + \gamma v(s^{\prime}) \right) ,\quad \forall (s,a) \in \mathbb{S} \times \mathbb{A}.\end{aligned}\end{eqnarray}

The Lagrangian of (10) is given by

(11) \begin{eqnarray} L_{\theta}(v,d)&=& \mu^\top v + \sum_{(s,a)\in\mathbb{S}\times\mathbb{A}} d(s,a) \left( \sum_{s^{\prime} \in \mathbb{S}} \mathcal{P}_{\theta}(s^{\prime}|s,a) \left( r(s,a,s^{\prime}) + \gamma v(s^{\prime}) \right) - v(s) \right),\end{eqnarray}

where the dual variable, $ d\triangleq \left( d(s,a) \right)_{(s,a)\in\mathbb{S}\times\mathbb{A}}\ge 0$ , is a non-negative vector of length $|\mathbb{S}||\mathbb{A}|$ . Let us introduce the multitask Lagrangian that integrates over the distribution of tasks:

(12) \begin{eqnarray} L(v,d)&\triangleq&\int_\Theta L_{\theta}(v,d) f(\theta) \ d\theta\notag\\&=& \mu^\top v + \sum_{(s,a)\in\mathbb{S}\times\mathbb{A}} d(s,a) \left( \sum_{s^{\prime} \in \mathbb{S}} \mathcal{P}(s^{\prime}|s,a) \left( r(s,a,s^{\prime}) + \gamma v(s^{\prime}) \right) - v(s) \right),\end{eqnarray}

where we have introduced a shortcut for the expected state transition distribution:

(13) \begin{eqnarray} \mathcal{P}(s^{\prime}|s,a)\triangleq \int_\Theta \mathcal{P}_{\theta}(s^{\prime}|s,a) f(\theta) \ d\theta.\end{eqnarray}

Note that (12) can be thought of as the Lagrangian of another LP, similar to (10) but where $\mathcal{P}_{\theta}$ has been replaced with $\mathcal{P}$ :

(14) \begin{align}& \underset{v}{\text{minimise}}\ \mu^\top v\nonumber\\[5pt]& \quad\text{s.t.} \quad v(s) \geq \sum_{s^{\prime} \in \mathbb{S}} \mathcal{P} (s^{\prime}|s,a) \left(r(s,a,s^{\prime})+ \gamma v(s^{\prime})\right),\quad \forall (s,a) \in \mathbb{S} \times \mathbb{A}.\end{align}

Indeed, problem (14) corresponds to a single MDP with transitions given by $\mathcal{P}$ , which represents a valid distribution, as shown by the following proposition.

Proof. Stochastic matrices lie in a compact convex set (Horn & Johnson, Reference Horn and Johnson1990, Theorem 8.7). Hence, their convex combination lies in the same set (Boyd & Vandenberghe, Reference Boyd and Vandenberghe2004, 24).

Since (14) satisfies Slater’s condition, strong duality holds (Boyd & Vandenberghe, Reference Boyd and Vandenberghe2004, Section 5.2.3), and optimal primal and dual variables are attained and form a saddle point of (12):

(15) \begin{eqnarray} \min_{v} \max_{d} L(v,d)&=& L(v^{\star}, d^{\star})= \max_{d} \min_{v} L(v,d),\end{eqnarray}

where $v^{\star}$ and $d^{\star}$ denote optimal primal and dual variablesFootnote ⁵ of (14), respectively.

There are multiple approaches to find a saddle point that satisfies optimality condition (15). We focus on the dual-ascent scheme (Arrow et al., Reference Arrow, Hurwicz and Uzawa1958), which consists in alternating between:

1. 1. finding a primal solution, given the dual variable and

2. 2. ascending in the direction of the gradient of the Lagrangian w.r.t. the dual variable, given the primal variable.

First, we show how to update the primal variable given d, that is

(16) \begin{eqnarray} v\leftarrow \arg\min_{v} L(v,d).\end{eqnarray}

The Karush–Kuhn–Tucker (KKT) conditions are sufficient for optimality in convex problems that satisfy Slater’s condition and have differentiable objective and constraints (Boyd & Vandenberghe, Reference Boyd and Vandenberghe2004, Section 5.5.3). These KKT conditions include the feasibility constraints, non-negativity of the dual variable for inequality constraints, complementary slackness, and null gradient of the Lagrangian w.r.t. the primal variable. Since problem (14) is linear, first-order conditions do not depend on v. Thus, the only condition that depends on v is complementary slackness:

(17) \begin{eqnarray} d(s,a) \left( \sum_{s^{\prime} \in \mathbb{S}} \mathcal{P}(s^{\prime}|s,a) \left( r(s,a,s^{\prime}) + \gamma v(s^{\prime}) \right) - v(s) \right)= 0,\quad\forall (s,a)\in \mathbb{S} \times \mathbb{A}.\end{eqnarray}

Similar to the standard single-task problem (recall Proposition 1), it can be shown (Puterman, Reference Puterman2005, Section 6.9) that our dual variable is the discounted state-action visitation measure:

(18) \begin{eqnarray} d(s,a)&=& \sum_{j\in\mathbb{S}}\mu(j) \sum_{t=0}^\infty \gamma^t p(s_t = s, a_t = a| s_0 = j),\end{eqnarray}

such that:

(19) \begin{eqnarray} \rho_\gamma^\pi(s)&=& \sum_{a\in\mathbb{A}} d(s,a).\end{eqnarray}

Therefore, finding d allows us to obtain the corresponding policy:

(20) \begin{eqnarray} \pi(a|s)= \frac{d(a,s)}{\sum_{a\in\mathbb{A}} d(s,a)}.\end{eqnarray}

Since $\pi(a|s) \ge 0$ and $ \sum_{s^{\prime} \in \mathbb{S}} \mathcal{P}(s^{\prime}|s,a) \left( r(s,a,s^{\prime}) + \gamma v(s^{\prime}) \right) - v(s)\le 0$ for all $(s, a) \in \mathbb{S} \times \mathbb{A}$ , we conclude that the Bellman equation, typically used to derive the critic in actor-critic methods, and given by

(21) \begin{eqnarray} v(s)&=& \sum_{a\in\mathbb{A}} \pi(a|s) \left( \sum_{s^{\prime}\in\mathbb{S}} \mathcal{P}(s^{\prime}|s,a) \left( r(s,a,s^{\prime}) + \gamma v(s^{\prime}) \right) \right),\quad \forall s\in\mathbb{S},\end{eqnarray}

is sufficient for (17), and thus to find the primal variable that optimises the Lagrangian.

Second, for the dual variable, we simply perform gradient ascent in the Lagrangian, yielding a recursion of the form:

(22) \begin{eqnarray} d&\gets& \left[ d + \beta \nabla_d L(v,d) \right]^+,\end{eqnarray}

where $\beta$ is the step size, $[\cdot]^+$ denotes projection on the non-negative orthant, and $\nabla_d $ denotes the gradient w.r.t. the dual variable d:

(23) \begin{eqnarray} \nabla_d L(v,d)&=& \left( \frac{\partial L(v,d)}{\partial d(s,a)} \right)_{ (s,a) \in \mathbb{S} \times \mathbb{A} }.\end{eqnarray}

Interestingly, note that the partial derivatives of the Lagrangian in (23) are equal to the so-named advantage function, $A:\mathbb{S}\times\mathbb{A} \rightarrow \mathbb{R}$ , which was originally motivated for learning to control continuous time systems approximated with small discrete time steps (Baird III, 1993) and, more recently, as a general variance reduction technique (Bhatnagar et al., Reference Bhatnagar, Sutton, Ghavamzadeh and Lee2009):

(24) \begin{eqnarray} \frac{\partial L(v,d)}{\partial d(s,a)}= A(s,a)&\triangleq& \sum_{s^{\prime} \in \mathbb{S}} \mathcal{P} (s^{\prime}|s,a) \left( r(s,a,s^{\prime}) + \gamma v(s^{\prime}) \right) - v(s).\end{eqnarray}

Since by learning $d^{\star}$ , we can obtain $\pi^{\star}$ from (20), the recursion in (22) can be seen as an actor update.

In summary, (21) and (22) define an actor-critic method for the tabular setting, with no need for parametric policies. This novel derivation shows that by finding a saddle point of the multitask Lagrangian (12), we obtain a solution to the original problem (2), as formally stated by the following proposition.

Proof. Consider $\mathcal{P}$ as the state transition of some MDP, then Theorem 6.9.4 from Puterman (Reference Puterman2005) states the following:

(25) \begin{eqnarray} \mu^\top v^\star&=& \sum_{s,a \in \mathbb{S} \times \mathbb{A}} d^\star(s,a) \sum_{s^{\prime}\in\mathbb{S}} \mathcal{P}(s^{\prime}|s,a) r(s,a,s^{\prime})= \max_\pi \mu^\top v^\pi,\end{eqnarray}

where $ v^\pi\triangleq \mathsf{E}_{\mathcal{P}, \pi} \left[ \sum_{t=0}^{\infty} \gamma^{t} r ( {\textbf{\textit{s}}}_t, {\textbf{\textit{a}}}_t, {\textbf{\textit{s}}}_{t+1}) \right]$ . From (25), applying (17) in (12), and using a relationship similar to (9) but for the multitask transition kernel, $\mathcal{P}$ , we have:

\begin{eqnarray*} L(v^\star, d^\star)&=& \max_\pi \mu^\top v^\pi\\&=& \max_\pi \int_{\mathbb{S}} \rho_\gamma^\pi(s) \int_{\mathbb{A}} \pi(a|s) \int_{\mathbb{S}} \mathcal{P} (s^{\prime}| s, a) r ( s, a, s^{\prime}) \ d s^{\prime} \ d a \ d s\\&=& \max_\pi \int_\Theta f(\theta) J_\theta(\pi) \ d\theta.\end{eqnarray*}

When we consider the empirical risk (3), the expected state transition distribution, $\mathcal{P}$ , can be approximated with this unbiased estimate:

(26) \begin{eqnarray} \overline{\mathcal{P}}(s^{\prime}|s,a)&\triangleq& \frac{1}{N} \sum_{k=1}^N \mathcal{P}_{\theta_k}(s^{\prime}|s,a),\quad \forall (s, a, s^{\prime}) \in \left( \mathbb{S} \times \mathbb{A} \times \mathbb{S} \right).\end{eqnarray}

From Proposition 1, we conclude that this is also a valid state transition distribution for some MDP. Hence, the same arguments hold for this average distribution, and we can derive a dual-ascent method to obtain the saddle point of an empirical approximation of the multitask Lagrangian (12) that averages (11) for the set of tasks $\left\{ \theta_k \right\}_{k=1}^N$ :

(27) \begin{eqnarray} \overline{L}(v,d)&=& \frac{1}{N} \sum_{k=1}^N L_{\theta_k}(v,d).\end{eqnarray}

It is trivial to see that the only difference between (12) and (27) is that the former uses the expected distribution $\mathcal{P}$ , while the latter uses its estimate $\overline{\mathcal{P}}$ . This yields the following corollary.

In the following subsections, we propose a diffusion-based fully distributed actor-critic architecture for large (possibly infinite) state-action sets, with parametric value function and policy that approximate the saddle point of (27).

4.2 Distributed critic

In the previous subsection, we have seen that the primal update of the dual-ascent method is equivalent to finding a value function that satisfies the multitask Bellman Equation (21).

When computing this value function for large or continuous state sets, it is commonFootnote ⁶ to rely on some parametric function approximation: $v_{\xi}(s) \approx v(s)$ , where $\xi \in \mathbb{R}^{M_v}$ is the parameter vector of length $M_v$ . Thus, for some given policy, $\pi$ , we can learn value function parameters $\xi$ by transforming (21) into a regression problem:

(28) \begin{eqnarray}{\underset{\xi}{\text{minimise}}}&&\quad \overline{J}(\xi)\triangleq \mathsf{E}_{\rho_\gamma^\pi} \left[ \left ( v_{\xi} \left( {\textbf{\textit{s}}}_t \right) - \overline{{\textbf{\textit{y}}}}_t \right )^2 \right],\end{eqnarray}

where the target values are given by:

(29) \begin{eqnarray} \overline{{\textbf{\textit{y}}}}_t&\triangleq& \int_{\mathbb{A}} \pi(a|s) \int_{\mathbb{S}} \overline{\mathcal{P}} (s^{\prime}|{\textbf{\textit{s}}}_t, a_t) \left( r({\textbf{\textit{s}}}_t, a_t, s^{\prime}) + \gamma v_{\xi}(s^{\prime}) \right) \ d s^{\prime} \ d a,\end{eqnarray}

This is equivalent to finding $\xi$ , such that the advantage function is as close to zero as possible.

In order to derive a diffusion-based distributed critic, we have to reformulate the problem as minimising the average cost over all tasks. The cost for each individual task takes the form:

(30) \begin{eqnarray} J_k(\xi)&\triangleq& \mathsf{E}_{\rho_\gamma^\pi} \left[ \left ( v_{\xi} \left( {\textbf{\textit{s}}}_{t} \right) - {\textbf{\textit{y}}}_{k,t} \right )^2 \right],\; k=1,\ldots,N,\end{eqnarray}

where ${\textbf{\textit{y}}}_{k,t}$ is the target for the kth task at time t:

(31) \begin{eqnarray} {\textbf{\textit{y}}}_{k,t}&\triangleq& \int_{\mathbb{A}} \pi(a|s) \int_{\mathbb{S}} \mathcal{P}_{\theta_k} (s^{\prime}|{\textbf{\textit{s}}}_{t}, a_{t}) \left( r({\textbf{\textit{s}}}_{t}, a_{t}, s^{\prime}) + \gamma v_{\xi}(s^{\prime}) \right) \ d s^{\prime} \ d a,\end{eqnarray}

such that: $ \overline{{\textbf{\textit{y}}}}_t= 1/N \sum_{k=1}^N {\textbf{\textit{y}}}_{k,t}$ .

We can use Jensen’s inequality to upper bound $J(\xi)$ by another function, $ \widetilde{J}(\xi)$ , and use this upper bound as surrogate cost:

(32) \begin{eqnarray} \widetilde{J}(\xi)&\triangleq& \frac{1}{N} \sum_{k=1}^N J_k(\xi)= \frac{1}{N} \sum_{k=1}^N \mathbb{E} \left[ \left ( v_{\xi} \left( {\textbf{\textit{s}}}_{t} \right) - {\textbf{\textit{y}}}_{k,t} \right )^2 \right]\ge \mathbb{E} \left[ \left ( \frac{1}{N} \sum_{k=1}^N \left( v_{\xi} \left( {\textbf{\textit{s}}}_{t} \right) - {\textbf{\textit{y}}}_{k,t} \right) \right )^2 \right]= \overline{J}(\xi).\qquad\end{eqnarray}

Now, we can apply diffusion to minimise $\widetilde{J}(\xi)$ in a distributed fashion, with every agent $k=1,\ldots,N$ , applying adaptation and combination steps in parallel:

(33a) \begin{equation} \widehat{\xi}_{k,i+1}= \xi_{k,i} - \alpha_{i+1} \widehat{\nabla}_\xi J_k (\xi_{k,i})\\\end{equation}

(33b) \begin{equation} \xi_{k,i+1}= \sum_{l \in \mathcal{N}_k} c_{lk} \widehat{\xi}_{l,i+1},\end{equation}

where i is the iteration index; $\alpha_i$ is the step size; $\widehat{\nabla}_\xi J_k (\xi_{k,i})$ is the stochastic gradient evaluated at $\xi_{k,i}$ and estimated from a batch of $T_{k,i}$ local samples, $\left\{ \left( s_{k,t}, a_{k,t}, r_{k,t+1}, s_{k,t+1} \right) \right \}_{t=0}^{T_{k,i}}$ , drawn from the stationary distribution induced by policy $\pi$ .

Equations (33a)–(33b) represent a template for a fully distributed critic update. Depending on how the targets are estimated, the sampling process and other factors, we can build different distributed critic methods. In addition, instead of using a simple stochastic gradient update in the adaptation step (33a), we can use more sophisticated methods, like momentum, adaptive learning rate, and other variants. In this paper, we will introduce two specific algorithms that use this template, Diff-SiAC and Diff-A2C. But before discussing their details, we present a template for the fully distributed actor update.

4.3 Distributed actor

Recall from Section 4.1 that the dual step of the dual-ascent method involves ascending in the direction of the gradient of the Lagrangian w.r.t. the dual variable.

For large or continuous state-action sets, it is convenient to approximate the policy with a parametric function. Let $\pi_w \approx \pi$ denote the parametric approximation of the actual policy, where $w \in \mathbb{R}^{M_\pi}$ is the parameter vector of length $M_\pi$ .

Replacing $\pi$ with $\pi_w$ in (27), we obtain an approximate Lagrangian, $ \widetilde{L}(v,w)\approx \overline{L}(v,d)$ :

(34) \begin{eqnarray} \widetilde{L}(v,w)&=& \mu^\top v + \int_\mathbb{S} \int_\mathbb{A} d_w(s,a) \overline{A}(s,a) \ ds\ da,\end{eqnarray}

where $d_w(s,a)$ is the resulting approximation of the dual variable:

(35) \begin{eqnarray} d_w(s,a)&\triangleq& \pi_w(a|s) \rho_\gamma^{\pi_w}(s),\end{eqnarray}

and $\overline{A}(\cdot)\triangleq 1/N \sum_{k=1}^N A_k(\cdot)$ refers to the average advantage function, with:

(36) \begin{eqnarray} A_k(s,a)&\triangleq& \int_{\mathbb{S}} \mathcal{P}_{\theta_k} (s^{\prime}|s,a) \left( r(s,a,s^{\prime}) + \gamma v(s^{\prime}) \right) d s^{\prime} - v(s).\end{eqnarray}

Thus, in order to approximate the optimal dual variable, we can move in the ascent direction of the gradient of (34) w.r.t. the policy parameter. The following theorem provides the required gradient.

Theorem 1 Theorem 1. The gradient of the Lagrangian w.r.t. the policy parameter is given by

(37) \begin{eqnarray} \nabla_w \widetilde{L} (v,w)= \int_{\mathbb{S}} \rho_\gamma^{\pi_w}(s) \int_{\mathbb{A}} \pi_{w}(a|s) \nabla_{w} \log \pi_{w}(a|s) \overline{A}(s,a) \ ds\ da.\end{eqnarray}

Proof. See Appendix C.1.

Interestingly, (37) is similar to previous policy gradient theorems (Sutton et al., Reference Sutton, Mcallester, Singh and Mansour1999), with the important difference that it yields the advantage function explicitly; while previous works motivated the advantage—as opposed to the state-action value function—as a variance reduction technique (Williams, Reference Williams1992; Bhatnagar et al., Reference Bhatnagar, Sutton, Ghavamzadeh and Lee2009).

In order to derive a fully distributed actor, we introduce the approximate Lagrangian for each individual task:

(38) \begin{eqnarray} \widetilde{L}_k(v,w)&\triangleq& \mu^\top v + \int_\mathbb{S} \int_\mathbb{A} \rho_\gamma^{\pi_w}(s) \pi_w(a|s) A_k(s,a) \ ds\ da,\end{eqnarray}

such that $ \widetilde{L}(\cdot)= 1/N \sum_{k=1}^N \widetilde{L}_k(\cdot)$ .

Similar to the critic, we can apply diffusion to perform the actor update, with step size $\beta_{i+1}$ :

(39a) \begin{equation} \widehat{w}_{k,i+1}= w_{k,i} + \beta_{i+1} \widehat{\nabla}_w \widetilde{L}_k(v_{\xi_{k,i}},w_{k,i}),\\\end{equation}

(39b) \begin{equation} w_{k,i+1}= \sum_{l \in \mathcal{N}_k} c_{lk} \widehat{w}_{l,i+1},\end{equation}

where $\widehat{\nabla}_w \widetilde{L}_k(v_{\xi_{k,i}},w_{k,i})$ is an estimate of each agent’s local policy gradient—which is similar to (37) but replacing the average advantage function, $\overline{A}$ , with each agent’s estimate of its local advantage function, A_k—evaluated at its local critic estimate, $v_{\xi_{k,i}}$ , obtained from (33a)–(33b).

Similar to the critic update, there are many ways of estimating the stochastic gradient in (39a). Depending on the way of estimating the advantage function (see Schulman et al., Reference Schulman, Moritz, Levine, Jordan and Abbeel2015 for multiple estimators); the sampling process; and how the value parameters, $\xi_{k,i}$ , relate to the policy parameters, we can obtain different fully distributed actor updates. These options lead to different actor-critic methods.

In the following subsections, we apply the Diff-DAC architecture to propose two actor-critic algorithms, which will allow us to demonstrate the benefits of Diff-DAC in terms of stabilisation, performance, generalisation and robustness.

4.4 Simple Actor-Critic (SiAC)

The first algorithms we introduce are centralised and Diff-DAC implementations of a SiAC algorithm, characterised by having a very simple and highly biased estimator of the advantage function that allows us to evaluate the stability provided by the diffusion mechanism. In particular, the parameters are only updated once the agent has completed an episode on each task. In order to be sample efficient, we perform as many updates to both critic and actor as available transitions in the episode. That is, if at the i-th iteration, the k-th agent samples an episode with $T_{k,i}$ transitions, then we obtain a set of $T_{k,i}$ advantage estimates given by

(40) \begin{eqnarray} \widehat{A}_{k,t}&\triangleq& \sum_{j=t}^{T_{k,i}} \gamma^{j-t} r_{k,j+1} - v_{\xi_{k,i}}(s_{k,t}),\quad0 \le t < T_{k,i}-1.\end{eqnarray}

Note that the advantage estimates $\left\{ \widehat{A}_{k,t} \right\}_{t=1}^{T_{k,i}}$ will be highly correlated, and can therefore cause learning to become unstable. This is done by design in order to conveniently study the stabilisation properties of the Diff-DAC architecture.

In order to compare the centralised and Diff-DAC architectures, we build two algorithms Centralised SiAC and Diff-SiAC where we introduce the following two changes: (i) Centralised SiAC has a single set of value and policy parameters, whereas Diff-SiAC has N sets of value and policy parameters (one per agent) and (ii) Centralised SiAC updates its set of value and policy parameters with advantage estimates calculated across all tasks whereas Diff-SiAC updates each agent’s parameters with its own local set of samples and then combines parameters with diffusion.

For Centralised SiAC, the value and policy parameters, $\xi_i$ and $w_i$ , are updated with stochastic gradients that average all samples and all advantage estimates from all tasks:

(41) \begin{eqnarray} \widehat{\nabla}_\xi \widetilde{J} (\xi_i, \pi_{w_i})&=& \frac{1}{T_i} \sum_{k=1}^N \sum_{t=0}^{T_{k,i} - 1} \nabla_\xi v_{\xi_i}(s_{k,t}) \widehat{A}_{k,t},\end{eqnarray}

(42) \begin{eqnarray} \widehat{\nabla}_w \widetilde{L} (v_{\xi_{i}},w_{i})&=& \frac{1}{T_i} \sum_{k=1}^N \sum_{t=0}^{T_{k,i} - 1} \nabla_{w} \log \pi_{w_{i}}(a_{k,t}|s_{k,t}) \widehat{A}_{k,t},\end{eqnarray}

where $T_i \triangleq \sum_{k=1}^N T_{k,i}$ , denotes the total number of samples from the ith episode of all tasks.

For Diff-SiAC, each agent updates its parameters, $\xi_{k,i}$ and $w_{k, i}$ , with stochastic gradients that average its local samples and advantage estimates:

(43) \begin{eqnarray} \widehat{\nabla}_\xi J_k (\xi_{k,i}, \pi_{w_{k, i}})&=& \frac{1}{T_{k,i}} \sum_{t=0}^{T_{k,i} - 1} \nabla_\xi v_{\xi_{k,i}}(s_{k,t}) \widehat{A}_{k,t},\end{eqnarray}

(44) \begin{eqnarray}\hspace*{15pt} \widehat{\nabla}_w \widetilde{L}_k (v_{\xi_{k, i}},w_{k, i})&=& \frac{1}{T_{k,i}} \sum_{t=0}^{T_{k,i} - 1} \nabla_{w} \log \pi_{w_{k,i}}(a_{k,t}|s_{k,t}) \widehat{A}_{k,t}.\hspace*{-15pt}\end{eqnarray}

While we have considered a standard stochastic gradient for the derivations, in practice we are free to use any gradient-based optimiser to perform parameter updates. In the experiments with Centralised SiAC and Diff-SiAC, we use the Adam optimiser (Kingma & Ba, Reference Kingma and Ba2015).

4.5 Diffusion A2C (Diff-A2C)

In this subsection, we introduce a Diff-DAC implementation of A2C that will allow us to evaluate a new regularisation effect that emerges from fully distributed sampling and learning.

A2C is a variant of the A3C algorithm described in Section 1 that uses distributed sampling but synchronous learning updates. In addition, A2C typically uses a more advanced multistep advantage estimator that reduces variance and can lead to faster learning:

(45) \begin{eqnarray} \widehat{A}_{k,t}&\triangleq& \sum_{j=t}^{T_{k, i}} \gamma^{j-t} r_{k,j+1} +\gamma^{T_{k,i}} v_{\xi_{k,i}}(s_{k,T_{k, i}}) - v_{\xi_{k,i}}(s_k, j),\quad0 \le t < T_{k}-1,\end{eqnarray}

where $T_{k,i}$ is a parameter and denotes the number of transitions per parameter update. Note that the multistep estimator (45) allows A2C agents to set $T_{k,i}$ to a fixed small value such that the parameters are updated at a fixed interval in terms of environment steps, instead of at the end of each episode. The distributed sampling approach, the multistep advantage estimates, and the quick updates allows A2C to offer stable and sample efficient learning. In typical A2C approaches, the training of a single set of parameters is centralised.

Since the advantage estimator in (45) relies on local samples and parameters, we are able to apply it to agents in the Diff-DAC architecture, with stochastic gradients similar to (41)–(44). This yields an algorithm we refer to as Diff-A2C wherein both experience collection and training are decentralised.

As with SiAC and Diff-SiAC we are free to choose the gradient-based optimiser. For the experiments with A2C and Diff-A2C we use RMSProp (Tieleman & Hinton, Reference Tieleman and Hinton2012) to demonstrate Diff-DAC working with varied optimisersFootnote ⁷. See Appendix D for pseudocode and a discussion contrasting Diff-SiAC and Diff-A2C.

6.1 Stability

We evaluate the stabilising properties of the Diff-DAC architecture by comparing Centralised SiAC versus Diff-SiAC on multitask variants of two classic control problems: inverted pendulum and cart-pole swing-up.

The inverted pendulum consists of a rigid pole and an actuated joint with limited torque. The goal is, starting from a random position, to take the pendulum to the upright position and balance. Cart-pole swing-up is an extension of cart-pole balance where the pole starts from the bottom and the goal is to swing the pole to the upright position and balance. The MRL problem consists of 25 tasks where we vary the pole mass and length for the inverted pendulum; and the pole mass, pole length and cart mass for cart-pole swing-up (see task details in Appendix A.1).

Our goal with these experiments is not to compare with state of the art centralised algorithms—which use several advancements to stabilise or improve performance—but to evaluate whether diffusion is an effective mechanism to stabilise learning. Thus, we compare Centralised SiAC versus Diff-SiAC, which are two versions of the same algorithm, described in Section 4.4, with the same advantage estimates and the same neural network architectures (agent details in Appendix A.1).

For Diff-SiAC, the network consists of $N=25$ agents (each agent is allocated one task), in a random strongly connected graph with average degree $|\overline{\mathcal{N}}| \triangleq \sum_{k=1}^N |\mathcal{N}_k| \approx 4.2$ . The connectivity matrix C was obtained with the Hastings rule (Sayed, Reference Sayed2014, 492) so that (6)–(7) hold. The random network topology aims to reflect the sparse connectivity that appears naturally when agents and data are geographically distributed—it is not related to any form of task similarity.

The results are reported as the return for all tasks, which is averaged over 10 test episodes per epoch and scaled by the maximum value achieved by any algorithm. Each epoch consists of five episodes per agent in Diff-SiAC, and 5N episodes in total for Centralised SiAC, so that both algorithms simulate the same number of episodes. Each experiment was repeated with six seeds. Figure 2 shows the median and first and third quartiles of the distribution of the return.

Figure 2

Stability. Learning curves from training with 25 randomly sampled tasks of inverted pendulum (left) and cart-pole swing-up (right). Plots show median and first and third quartiles of the return averaged over all tasks, and six seeds. Centralised SiAC (red) is unstable, while Diff-SiAC (blue) learns robustly.

We observe that Centralised SiAC starts learning faster than Diff-SiAC in multitask inverted pendulum (left), and achieves near maximum performance for both problems. Faster learning under the centralised architecture is expected since it can compute the gradients with data from all tasks at every iteration, while Diff-SiAC has to wait until the parameters are diffused across the network. However, Centralised SiAC is unstable in both problems, which is also expected since the samples used to estimate the gradients are highly correlated and Centralised SiAC has no decorrelation mechanism.

Diff-SiAC converges more slowly but is much more stable in both problems. Recall that Centralised SiAC and Diff-SiAC have the same network architecture, sample from multiple environments in parallel and are trained with the same amount of data in total. We therefore believe that this enhanced stability is due to a bias removal effect on the sampling distribution introduced by the diffusion mechanism, similar to the distributed exploration capabilities exhibited when applying diffusion to off-policy evaluation (Valcarcel Macua et al., Reference Valcarcel Macua, Chen, Zazo and Sayed2015).

We performed similar experiments for the single-task problem—where Centralised SiAC learns from multiple copies of the same task, and all Diff-SiAC agents train on copies of the same task—and observed the same stability improvement (see results in Appendix B).

The instability of Centralised SiAC might be alleviated in multiple ways, like adding a replay buffer (Mnih et al., Reference Mnih, Kavukcuoglu, Silver, Graves, Antonoglou, Wierstra and Riedmiller2013; Lillicrap et al., Reference Lillicrap, Hunt, Pritzel, Heess, Erez, Tassa, Silver and Wierstra2015). Our goal with these experiments is precisely to show that diffusion can be used as an alternative stabilisation technique.

6.2 Comparison with Dist-MTPS

We compare Diff-SiAC with Dist-MTPS on an MRL extension of the standard cart-pole balance problem, which is the only environment considered in this paper that is controllable with linear policies learnt from raw data. The agents have to learn $N=25$ tasks, characterised by different pole masses and lengths (see Appendix A.2 for details).

In particular, we compare against two variants of Dist-MTPS, which vary by their use of differing policy search methods: REINFORCE (Williams, Reference Williams1992) and PoWER (Kober & Peters, Reference Kober and Peters2009).

Figure 3 shows that Diff-SiAC learns faster and reaches higher return than Dist-MTPS REINFORCE. Dist-MTPS PoWER converges faster than Diff-SiAC, however, the return of the latter is significantly higher. This is remarkable since Dist-MTPS learns a different policy for each task, while Diff-DAC agents learn a single policy for all tasks.

Figure 3

Multitask cart-pole balance with continuous action space. Centralised SiAC learns faster than the distributed approaches and achieves similar performance to Dist-MTPS REINFORCE, but Diff-SiAC achieves the best asymptotic performance and with lower variance. Each epoch consists of five episodes per agent in Diff-SiAC, and 5N episodes for Dist-MTPS and Centralised SiAC, so that all algorithms run the same number of episodes. Results are averaged over tasks and five seeds.

We also compare with Centralised SiAC in this example. Consistent with the stability experiments, Figure 3 shows that Diff-SiAC learns more slowly but with lower variance than Centralised SiAC. In addition, we observe a new effect: Diff-SiAC clearly achieves higher performance than the centralised architecture. This is a very interesting feature of the diffusion mechanism that has been already reported for non-convex optimisation problems (Valcarcel Macua, Reference Valcarcel Macua2017, Chapter 4). We believe this is due to a new form of regularisation, which we explore further in the next subsection.

6.3 Regularisation

We extend our analysis to multitask variants of two more challenging and higher dimensional environments: Acrobot and MuJoCo Hopper.

In Acrobot the agent must learn a policy to swing a two-link robot from its initial position, approximately hanging down, to a goal position of balancing straight upwards. The randomisation of the environment dynamics generates tasks by sampling the length, mass and inertia of the robot uniformly from a distribution centred on the values of the standard Acrobot environment. This formulation was originally introduced by Packer et al. (Reference Packer, Gao, Kos, Krähenbühl, Koltun and Song2018). We design a MRL problem by sampling 25 tasks (see Appendix A.3 for details).

The objective in MuJoCo Hopper is to learn a policy to keep the agent from falling over and to enable the agent to move as quickly as possible in any direction. We implement 2 MRL problems, consisting of 25 tasks each. In one set of experiments, we change the mass of the agent for each task. The second set of experiments introduces wind. We change the direction and intensity of the wind for each task (see Appendix A.3 for details).

The randomisation of the environment parameters—pole mass, pole length, and inertia for Acrobot and agent mass and wind speed and direction for Hopper—is calibrated to generate an MRL problem more challenging than the original single-task environments.

For these MRL problems, we compare 3 agent implementations: (i) Diff-A2C on a network of $N=25$ agents, each one with a single process sampling from one of the tasks; (ii) Centralised A2C where 1 agent has 25 processes, 1 per task, so it simultaneously learns from experience collected on all tasks; and (iii) Specialised A2C agents which train on each of the tasks individually but each one with the equivalent resources to the Centralised A2C agent (i.e., each of the 25 specialised agents assigned 25 copies to one of the sampled environments).

The comparison of Diff-A2C and Centralised A2C enables us to compare two learning architectures using approximately the same amount of computation. Centralised A2C centralises learning while maintaining decentralised sampling from environments run in parallel. Diff-A2C decentralises both sampling and learning. The specialised agents provide an upper bound to performance during training thereby offering an opportunity to evaluate the performance gap incurred by the multitask agents.

For this set of experiments, all agents are trained using the RMSProp optimiser (Tieleman & Hinton, Reference Tieleman and Hinton2012). This provides an opportunity to show that the Diff-DAC architecture is optimiser agnostic in practice—although it is derived and analysed assuming vanilla stochastic gradient descent. Indeed, we attain similar results when running the experiments presented here with the Adam optimiser. Full details of agent hyperparameters are provided in Appendix A.

The ring topology is used for Diff-A2C in this section. This topology can be challenging due to the sparsity of the connectivity, which implies a slower diffusion rate (it takes up to 12 iterations to diffuse each agent’s parameters to every other agent) and less robust communication (there are only 2 possible paths between every pair of agents).

Figure 4 displays the results for experiments on the Acrobot environments. Diff-A2C and Centralised A2C achieve the same final performance in training while the specialised agents achieve slightly greater ultimate performance. The optimality gap is small, meaning that both Diff-A2C and Centralised A2C learn a single policy that is expressive enough to control the 25 tasks near optimally. Consistent with previous experiments, we see that Centralised A2C learns faster initially. In this case, however, Centralised A2C does not exhibit stability issues, as A2C’s decentralised sampling stabilises the sampling distribution, similar to the stabilising effect of the Diff-DAC architecture.

Figure 4

Regularisation Acrobot. Learning curves from training with 25 randomly sampled tasks of Random Extreme Acrobot. For each experiment, we average performance over all 25 tasks. The plot shows the average $\pm$ 1 standard error over 8 seeds. Centralised A2C learns faster. Diff-A2C achieves similar performance to Centralised A2C. Specialised agents achieve the highest performance, but with small gap.

Figure 5

Regularisation MuJoCo Hopper. Learning curves from training with 25 randomly sampled tasks of Random Mass (left) and Random Wind (right) MuJoCo Hopper. For each experiment, we average performance over all 25 tasks. The plots show the average $\pm$ 1 standard error (of averages) over 8 seeds. Specialised agents achieve the highest performance, with a significant gap w.r.t. to the other agents. Diff-A2C agents clearly outperform Centralised A2C.

Figure 5 shows results for the two MRL problems with MuJoCo Hopper: random mass and random wind. These are significantly more challenging tasks than Acrobot. We observe the pattern of initially fast learning for the centralised architecture. But now we can clearly see that the optimality gap is smaller for Diff-A2C in both set of experiments. This supports the hypothesis that diffusion induces some form of regularisation effect that allows the agents to find a better policy that can control the set of tasks more effectively.

Table 1

Parameter similarity. Relative deviation of final parameters of trained agents. This is determined by calculating the mean and the standard deviation of each parameter of the trained agent over 25 agents (1 per task). The standard deviations are then divided by the mean. The reported values are the average over the parameters and over eight seeds.

However, since each Diff-A2C agent maintains its own policy, it is not clear whether the performance improvement over the centralised architecture is due to finding a better policy or to being able to exploit policies specialised to each task. In order to investigate, we look at how similar the policies learnt by the Diff-A2C agents are in terms of parameters and behaviour on the tasks used in training. If the policies of all Diff-A2C agents are equal, then we can be sure that the policy found via Diff-A2C is better than that found by Centralised A2C.

Table 1 shows the relative deviation of the parameters as a measure of the similarity of the agents at the end of training. For Diff-A2C and specialised agents, the value is calculated by dividing the standard deviation by the mean of each model parameter across all agents, then averaging the results over all parameters, and finally averaging over eight runs with differing random seeds. The results show that all Diff-A2C agents converge to very similar policy networks. On the other hand, the specialised agents converge to policy networks that are significantly different from each other. This is indeed consistent with Theorem 2, which shows almost certain asymptotic agreement amongst the agents, and supports the hypothesis that diffusion allows us to find a single policy that performs better than the one found by the centralised architecture.

In order to further validate the convergence of Diff-A2C agents to a common solution, we ran each of the 25 trained agents on the task they were trained on as well as the tasks of all other agents in the network. On average, agents achieved 0.07% ( $\pm$ 3.4) higher return, over 10 episodes, in the task they were trained on compared to the tasks of their peers (result averaged over all agents and 8 random seeds). Since the performance difference is not statistically significant, we conclude the small deviations in the policy parameters are not significant.

The above analysis suggests that the policy learnt by diffusion should be better able to generalise across tasks than the one found by the centralised architecture. To consider the question of generalisation, we performed a zero-shot learning experiment in the Acrobot environment, evaluating our trained agents on newly sampled environments (details of these environments are provided in Appendix A.4). Results are presented in Table 2, and show that Diff-A2C yields agents better able to generalise to new environments. The Centralised A2C agents show some ability to generalise to new environments but achieve lower returns in the evaluation when compared to Diff-A2C despite attaining near identical performance at the end of training. Unsurprisingly, the specialised agents do not generalise well. Specialised agents attain returns approximately 33% higher than Diff-A2C agents on the environment in which they specialise but are outperformed by 31% and 25% when transferred to held out easy and hard environments, respectivelyFootnote ⁹.

Figure 6

Network topology. Influence of network topology in single-task cart-pole balance with continuous action space. Diffusion is able to combine the experience of all agents in a way that is relatively insensitive to network sparsity. Moreover, by increasing the number of agents, we obtain higher performance, suggesting Diff-SiAC is able to find a better local optimum. Results are averaged over all agents and five seeds.

Table 2

Zero-shot learning. Evaluation performance for trained agents on unseen Acrobot tasks. The values are averages over 8 seeds and 10 episodes each. For the specialised and Diff-A2C agents, a single agent from each experiment was chosen at random and evaluated on the environment they were trained on as well as the same previously unseen easy and hard environments. Values in brackets denote a 95% confidence interval.

6.4 Network dependence

In this section, we perform experiments to study the influence of the communications network on the performance of the proposed Diff-DAC architecture. First, we evaluate the impact of the network topology by varying the size of the graph and its neighbourhoods. We then explore the impact of noisy or intermittent links on agent performance.

Figure 7

(Noisy links) Learning trajectories of Diff-A2C agents with differing probabilities of links being dropped at an update step. The probability, denoted by p, parameterises independent Bernoulli distributions, one per connection. Experiments conducted with 14 agents connected in a ring topology. The plots show performance averaged over all agents in the graph and averaged over 8 seeds.

We evaluate the impact of the network topology with Diff-SiAC agents learning the single-task cart-pole balance problem, where all agents operate in different copies of exactly the same environment (see details in Appendix A.4). Figure 6 shows that for the same network size, $N=25$ , a relatively sparse network, $|\overline{\mathcal{N}}| \approx N/6$ , learns slightly more slowly but achieves performance similar to a more dense network, $|\overline{\mathcal{N}}| \approx N/3$ . This is consistent with the theoretical analysis that shows that as long as the connectivity matrix, C, satisfies conditions (6)–(7), asymptotic performance is guaranteed independent on the network sparsity. From a practical point of view, this is a promising result that suggests that communication and computational costs per agent can be reduced without penalising performance, since they scale with the number of neighbours. In addition, we see that larger number of agents $N=100$ improves the final performance, suggesting that the regularisation effect discussed in Section 6.3 is stronger with a larger number of agents.

Finally, we consider the impact of failing links on training in the original (single-task) Acrobot and MuJoCo Hopper environments. These experiments emulate issues of noisy or interrupted message passing, typically seen in real deployments. As shown in Figure 7, as the probability of any link in the network failing at a given update step increases, the Diff-A2C agents’ learning is slowed. However, the agents converge towards similar final performance. This shows that diffusion is robust to failed links even when the failure rate is as high as 80%. This was predicted in Section 5, where we discuss that conditions on the connectivity matrix need only hold in expectation. The Diff-A2C experiments were conducted with a ring topology meaning that dropped links easily cause the graph to become disconnected. We would therefore expect this topology to be particularly vulnerable to dropped links. In the case of a centralised agent, however, should a single environment instance fail, the agent’s learning is liable to fail completely unless explicit countermeasures are introduced.