# Federated Reinforcement Learning at the Edge

Konstantinos Gatsis  The author is with the Department of Engineering Science,
University of Oxford, Parks Road, Oxford, OX1 3PJ, UK. Email:
<EMAIL_ADDRESS>
###### Abstract

Modern cyber-physical architectures use data collected from systems at
different physical locations to learn appropriate behaviors and adapt to
uncertain environments. However, an important challenge arises as
communication exchanges at the edge of networked systems are costly due to
limited resources. This paper considers a setup where multiple agents need to
communicate efficiently in order to jointly solve a reinforcement learning
problem over time-series data collected in a distributed manner. This is posed
as learning an approximate value function over a communication network. An
algorithm for achieving communication efficiency is proposed, supported with
theoretical guarantees, practical implementations, and numerical evaluations.
The approach is based on the idea of communicating only when sufficiently
informative data is collected.

##  I Introduction

Recent years have seen a shift in cyber-physical system architectures from
systems running in isolation or local networks to systems connected to the
cloud for outsourcing data and computations. This has given rise to the
realization that the resulting bandwidth and communication requirements can
become a bottleneck, and as a result, computing at the edge of the
architecture is explored. Learning and adapting to data from sensors, robots,
or vehicles located at the edge enable new applications such as cloud robotics
[1], connected autonomous transportation systems, and the Industrial Internet-
of-Things. Toward this end, this paper introduces a new framework for
performing distributed reinforcement learning from data collected locally at
individual agents/robots at the edge.

The accelerating developments in machine learning and reinforcement learning
have increased the interest of the control community in using data-driven
techniques. Specifically in the area of control of distributed and multi-agent
systems, very recent developments include algorithms for multi-agent
reinforcement learning [2, 3, 4], reinforcement learning over networks/graphs
[5, 6, 7, 8], as well as the search for appropriate parameterizations for
these problems [9]. However when dealing with distributed learning at the
edge, there is also the need for communication efficiency, especially if
agents have high dimensional time-series data and operate over resource-
limited communication networks.

The bulk of research in the area of distributed and communication-efficient
learning, also termed federated learning, is focused on static machine
learning problems, such as classification. To overcome the communication
bottleneck of sending high dimensional data, the main idea is to send
gradients of the objective with respect to the parameters being learned,
instead of the data itself. Approaches based on gradient quantization and non-
periodic updates [10, 11, 12], allocation of wireless resources [13, 14], or
approaches exploiting the informativeness of the data [15, 16] are being
explored. For the problem of communication-efficient reinforcement learning,
only now initial approaches emerge, including non-periodic updates for policy
gradient methods [17], distributed peer-to-peer network architectures [18],
specific problems such as multi-armed bandits [19], or regret analysis of
online distributed reinforcement learning [20].

Access Point Learned Weights $w$Agent 1Agent 2 … Agent mConnectivity Layer

Figure 1: Architecture for distributed reinforcement learning tasks over
networks of agents. Agents are collecting state transition data and are
communicating with an access point/server in order to learn a common model.
Communication efficiency is achieved by communicating when data are more
informative.

This paper introduces a new approach for communication-efficient reinforcement
learning problems. To avoid costly exchange of time-series data, agents should
assess how informative are the data they collect, and communicate if the
update will help the process of learning. The setup, described in Section II
and shown in Fig. 1, involves multiple agents collecting state transitions and
costs in a distributed manner for the purpose of learning approximate value
functions, which is a central problem in reinforcement learning. Specifically
linear value function approximation is considered. While all recent approaches
[17, 18, 19, 20] try to limit the amount of communication exchange during
reinforcement learning, the main novelty of this paper is that the
communication cost is part of the performance criterion, and the resulting
advantage is that algorithms which by design efficiently tradeoff
communication and learning are developed. This is obtained both theoretically
(Section III) as well as in numerical examples in finite and continuous state
spaces (Section V).

The approach adapts ideas from the author’s recent work on communication-
efficient linear regression [15, 16] to the reinforcement learning problem. On
the technical side, the approach is different here as, to ensure convergence
close to an optimal solution, the agents increasingly send less informative
data as the number of iterations of the learning algorithm grows. More
broadly, the technical methodology relates to the problem of efficient control
over networks [21, 22], event-triggered learning [23, 24] and resource-aware
optimization [25, 26, 27, 28].

##  II Problem Setup

The architecture examined in this paper, shown in Fig. 1, involves an access-
point/server interested in solving a reinforcement learning task on data that
are collected by multiple agents. Specifically, each agent is collecting
independently state transitions (from a state $x^{t}$ to a new state
$x^{t}_{+}$) and cost measurements (of the form $c^{t}$ at state $x^{t}$), and
communicate with the server in order to jointly learn an approximate value
function $V(x)$ parameterized by a vector of weights $w$. The aim will be to
achieve this with communication efficiency, i.e., without agents communicating
all collected data all the time. An example scenario is presented, and the
formal mathematical formulation follows next.

######  Example 1 (Motivating scenarios).

As a first example, suppose the agents in Fig. 1 are robots/drones/vehicles
with identical system dynamics. Then they can each collect data from their own
trajectories (state transitions) as well as costs measuring how well they can
achieve a common task, such as tracking a desired behavior. Transmitting all
these data over the communication network would be costly. A recent case study
of this form by Google [29] considers the large scale training of control and
manipulation policies using multiple robots collecting image data
concurrently. As a second example, suppose the agents in Fig. 1 are
sensors/actuators in an industrial setting collecting time-series data from
multiple identical physical processes, for the purpose of improving the
control of the processes.

###  II-A Mathematical Problem Formulation

We assume a Markov Decision Process problem defined by the state space $X$,
the action space $A$, the transition probabilities
$\mathbb{P}(x_{+}{\,\big{|}\,}x,a)$111or alternatively general state dynamics
of the form $x_{+}=f(x,a,w)$ for some noise variable $w$, and a cost function
$c:X\times A\rightarrow{\mathbb{R}}$ giving rise to costs of the form
$c_{k}=c(x_{k},a_{k})$. We are interested in approximating the value function,
or cost-to-go function of a given policy $a_{k}=\pi(x_{k})$, defined as
$V(x):=\mathbb{E}\left[\sum_{k=0}^{\infty}\gamma^{k}c(x_{k},a_{k}){\,\big{|}\,}x_{0}=x\right]$
with a discount factor $\gamma\in(0,1)$. A general theoretical approach for
finding the value function is to perform the Value Iteration Algorithm, which
iteratively fixes a current guess of the value function
$V^{\text{current}}(x),x\in X$, and updates it according to

$\displaystyle V^{\text{updated}}(x)$ $\displaystyle=c(x,\pi(x))$
$\displaystyle+\gamma\,\mathbb{E}[V^{\text{current}}(x_{+}){\,\big{|}\,}x,a=\pi(x)]$
(1)

for all points $x\in X$, and repeats the process again and again. Under
technical conditions[30, Vol. II, Ch. 2], this process can converge to the
desired value function $V(x)$, which is a fixed point of II-A (Bellman
equation).

In reinforcement learning and approximate dynamic programming, this iteration
is performed approximately, using data collected by following the given
policy. The data consists of multiple state transitions from states
$x^{t},t=0,1,2,\ldots$ to new states $x^{t}_{+},t=0,1,2,\ldots$, following the
above transition probabilities, and stage costs of the form $c^{t}$ at state
$x^{t},t=0,1,2,\ldots$. In general we can denote these as tuples
$(x^{t},c^{t},x_{+}^{t}),t=0,1,2,\ldots$. In practice, these state transitions
can be just segments from longer state trajectories. The state samples
$x^{t},t=0,1,2,\ldots$ are modeled as drawn from a distribution $d(x)$ in this
paper.

Moreover, instead of computing the updated value function in II-A in the space
of all functions $\\{V:X\rightarrow{\mathbb{R}}\\}$, a restricted function
class is selected. In this paper we follow the commonly employed linear
function class [31, 30]. In other words, we are trying to explain
$V^{\text{updated}}(x)$ in II-A as a linear combination of basis functions
(features) as

$V^{\text{updated}}(x)\approx\sum_{i=1}^{n}w_{i}\phi_{i}(x).$ (2)

Here $w\in{\mathbb{R}}^{n}$ if the vector of weights (linear combination) to
be learned, consisting of elements $w_{i}$, and $\phi_{i}(x)$ are fixed basis
functions (not learned). Examples of general basis functions, especially when
$X$ is a real vector space, include discretization functions, polynomial
functions, radial basis functions, and others [31, 30].

To pick one particular approximation in 2, we are interested in minimizing the
squared error

$\underset{w\in{\mathbb{R}}^{n}}{\text{minimize}}\;J(w)=\mathbb{E}_{d}\left[V^{\text{updated}}(x)-\sum_{i=1}^{n}w_{i}\phi_{i}(x)\right]^{2}$
(3)

where the expectation is with respect to a distribution $d(x)$, which
corresponds to the distribution of the data collected by the agents. To sum
up, instead of updating the value function according to II-A, we instead
approximately update to the function $\sum_{i=1}^{n}w^{*}_{i}\phi_{i}(x)$
where $w^{*}$ is the vector solving 3. After this approximation is found, the
process II-A repeats. The current value function is reset and a new
approximation is computed.

A fundamental question then is how to solve problem 3 from data. An approach
is to perform what can be considered a stochastic gradient descent.
Specifically, this in an iterative algorithm of the form

$w_{k+1}=w_{k}-\varepsilon\hat{\nabla}J(w_{k}),\;k=0,1,\ldots$ (4)

where $\varepsilon>0$ is a stepsize, and the gradient is approximated from the
data tuples as

$\displaystyle\hat{\nabla}J(w_{k})=\frac{1}{T}\sum_{t=0}^{T}\phi(x^{t})\left(w_{k}^{T}\phi(x^{t})-c^{t}-\gamma
V^{\text{current}}(x_{+}^{t})\right).$ (5)

In this expression, $k$ refers to iterations of the algorithm 4, while $t$
refers to identically distributed samples of state transitions and costs from
the Markov Decision Process, and there are $T$ of them in total. It can be
verified that this yields an unbiased estimate of the gradient of 3. After a
large number of iterations $N$ of 4, which also means after drawing many data
samples, and with an appropriate stepsize explained below, the iterate $w_{N}$
will converge close to the optimal solution of the problem 3 which we denote
as $w^{*}$.

######  Remark 1 (Relation to other Reinforcement Learning Approaches).

In this paper we illustrate how the above value function approximation in 3
can be performed with communication efficiency. This approximation then needs
to be performed at each iteration of the value iteration algorithm II-A – see
also Algorithm 1. The approach can also be extended to learn a Q-function
approximation but this is not further discussed in this paper due to limited
space. More broadly, these algorithms are variants of Projected Value
Iteration [30, Vol. II, Ch. 6], and are behind many successful reinforcement
learning approaches [32, 33]. These algorithms are attractive because under
technical conditions they converge to a unique point.

###  II-B Communication-efficient reinforcement learning problem

Given the above modeling for a reinforcement learning task that needs to be
solved, the communication problem is as follows. At each iteration $k$, the
server broadcasts the current weights $w_{k}$ to all agents. Then each agent
$i$ collects $T$ local data samples identically distributed (across samples
and across agents), computes a local stochastic gradient
$\hat{\nabla}_{i}J(w_{k})$ from the available local data using formula 5, and
decides whether to transmit this gradient update over the communication
network to the receiving server. The server updates the current vector of
weights $w_{k}$ depending on the information received from different agents.
For simplicity of exposition the case of two agents is considered and
theoretically analyzed, and experiments with more agents are conducted
numerically in Section V. This leads to the update rule at the server

$w_{k+1}=\left\\{\begin{array}[]{ll}w_{k}-\varepsilon\hat{\nabla}_{1}J(w_{k})&\text{if
$1$ transmits}\\\ w_{k}-\varepsilon\hat{\nabla}_{2}J(w_{k})&\text{if $2$
transmits}\\\
w_{k}-\frac{\varepsilon}{2}(\hat{\nabla}_{1}J(w_{k})+\hat{\nabla}_{2}J(w_{k}))&\text{if
both transmit}\\\ w_{k}&\text{if no transmits}\end{array}\right.$ (6)

We further denote with $\alpha_{k}^{i}\in\\{1,0\\}$ the decision for each
agent $i=1,2$ to transmit or not.

At the next iteration $k+1$ a new set of data is collected at each agent, a
new stochastic gradient direction $\hat{\nabla}_{i}J(w_{k+1})$ with respect to
the new vector $w_{k+1}$ is computed at each agent, and the process repeats
until a final iteration $N$. The algorithm is also described in Algorithm 1.

The aim will be to avoid sending updates all the time in order to limit the
communication burden. Hence we consider the average communication cost during
all iterations and across all agents as

$\frac{1}{N}\sum_{k=0}^{N-1}\,\frac{\alpha_{k}^{1}+\alpha_{k}^{2}}{2}$ (7)

On the other hand, we want to understand the progress of learning, hence we
also measure how well the final set of weights $w_{N}$ solves 3, in other
words we measure the cost function $J(w_{N})$.

We note that since the data points at each iteration and at each agent are
random, so are the constructed stochastic gradient directions, and so are the
vectors $w_{k}$, and so are the decisions $\alpha_{k}^{i}$ of the agents to
transmit. We propose then to measure the efficiency of the implementation on
average over the data points collected. As a result, we establish the
performance metric

$\mathbb{E}_{\text{data}}\left[\lambda\sum_{k=0}^{N-1}\,\frac{\alpha_{k}^{1}+\alpha_{k}^{2}}{2N}+J(w_{N})\right]$
(8)

Here $\lambda>0$ is a tuning parameter that is used to either penalize
communication or learning performance. It is worth emphasizing then that there
are two expectations in this paper. One is the integral defined in the
objective $J(w)$ in 3, and another is the expected performance of the
implementation in 8 computed as an integral over tuples
$x^{t},c^{t},x_{+}^{t+1}$ – in total $2NT$ tuples over agents, iterations, and
samples – and denoted as $\mathbb{E}_{\text{data}}$ to clarify the difference.

##  III Theoretical scheme for communication-efficient reinforcement learning

Algorithm 1 Distributed Approximate Value Iteration Algorithm

1:Fix a policy $\pi$

2:Fix current value function guess $V^{\text{current}}(x)$.

3:Fix initial weights $w_{0}$ at server

4:for Iteration $k=0,1,2,\ldots,N-1$ do

5: Server transmits weights $w_{k}$ to agents

6: At each agent $i$ collect $T$ state transition samples following policy
$\pi$

7: At each agent $i$ compute stochastic gradient $\hat{\nabla}_{i}J(w)$

8: At each agent $i$ implement communication 9 with the approximation IV

9: At the server, update weights according to 6

10:end for

11:Set $V^{\text{updated}}(x)\leftarrow\sum_{i=1}^{n}w_{N}(i)\phi_{i}(x)$
using the final weights $w_{N}$

12:Replace $V^{\text{current}}(x)\leftarrow V^{\text{updated}}(x)$ and go to
Step 3

The approach is based on the notion of performance gain which can be thought
as a measure of how informative are the data collected at each agent at each
time step with respect to the reinforcement learning problem. The gain at
agent $i=1,2$ can be calculated by measuring how much will the objective
change if the agent sends the update. Whether this gain is negative or
positive depends on the random direction of the update. The proposed approach
then is to send a gradient update if the gain is large enough. Mathematically
we write

$\alpha_{k}^{i}=\left\\{\begin{array}[]{ll}1&\text{if
}J(w_{k}-\varepsilon\hat{\nabla}_{i}J(w_{k}))-J(w_{k})\leq-\frac{\lambda}{\rho^{N-1-k}}\\\
0&\text{otherwise}\end{array}\right.$ (9)

where the scalar parameter $\lambda>0$ is the one defined in the performance
criterion, and $\rho\in(0,1)$ is a parameter – whose impact is further
discussed in the theoretical results below. Intuitively this approach saves up
communication resources, because the updates will be infrequent. Moreover, the
term at the right hand side, which measures how informative are the data at
the current iteration, is decreasing (in absolute value) as the number of
iterations grow. Hence, at the beginning only very informative updates are
transmitted, while as learning progresses, less informative updates are
transmitted as well.

######  Assumption 1.

The $n\times n$ symmetric matrix $\mathbb{E}_{d}\phi(x)\phi(x)^{T}$ is
positive definite.

This assumption guarantees the solution to the main problem 3 is unique.

######  Assumption 2.

The step size $\varepsilon>0$ in 6 satisfies

$\left|1-2\varepsilon\lambda_{i}(\mathbb{E}_{d}\phi(x)\phi(x)^{T})\right|<1$
(10)

for all eigenvalues of the matrix at the right hand side.

This assumption guarantees the step size is small enough so that convergence,
even without communication constraints, is satisfied. A sufficient condition
is $\varepsilon<2/\lambda_{\max}$ where $\lambda_{\max}$ is the largest
eigenvalue of the above matrix. Assumption 1 guarantees that 10 can be met.

######  Assumption 3.

The parameter $\rho$ in 9 satisfies

$\rho\geq\max_{i}(1-2\varepsilon\lambda_{i}(\mathbb{E}_{d}\phi(x)\phi(x)^{T}))^{2}$
(11)

for all eigenvalues of the matrix at the right hand side.

This assumption states that measuring the informativeness of the data should
decrease at a sufficiently slow rate. Assumptions 2 and 3 together guarantee
that $\rho<1$ is a possible choice.

The main theoretical result of this paper is established next.

######  Theorem 1 (Communication-Efficient Value Function Approximation).

Consider the optimization problem defined in 3. Consider the update rule in 6.
Suppose $\hat{\nabla}_{i}J(w_{k}),i=1,2,$ are independent random variables
with mean equal to $\nabla J(w_{k})$ and covariance $G$ at each iteration $k$.
Consider the communication strategy in 9 with a fixed number of iterations
$N$. Let Assumptions 1-3 hold. Then we have that

$\displaystyle\mathbb{E}_{\text{data}}\left[\lambda\sum_{k=0}^{N-1}\frac{\alpha_{k}^{1}+\alpha_{k}^{2}}{2N}+J(w_{N})\right]\leq\lambda+J(w^{*})$
$\displaystyle+\rho^{N}[J(w_{0})-J(w^{*})]+\frac{1-\rho^{N}}{1-\rho}\varepsilon^{2}\text{Tr}(\mathbb{E}_{d}\phi(x)\phi(x)^{T}G)$
(12)

where $w^{*}$ is the optimal solution of 3 and the expectation is with respect
to the data collected until iteration $N$.

We have the following observations. The terms on the right hand side of 1
measure the suboptimality of learning, including the terms that have to do
with the poor initialization $J(w_{0})-J(w^{*})$ and the noise of the
gradients captured by the matrix $G$. As the number of iterations $N$ grows,
the impact of the former is diminished, and only the latter remains. This
expression also suggests that ideally one would pick the parameter $\rho$ to
be the minimum allowed by the above Assumption 3.

The theorem characterizes the tradeoff between communication and learning. By
increasing the parameter $\lambda$, there is a higher penalty for
communicating, and as a result, the agents communicate less often — see
following remark. As a consequence, learning performance will be impacted. But
the above theorem guarantees by design that there will be a graceful
compromise between communication performance and learning – the left hand side
1 cannot be arbitrarily poor.

It is worth noting that, essentially, from the right hand side of 1, the
theorem states that the aggregate performance will be better than just having
one agent only and transmitting all the time. It is possible to extend the
analysis to get bounds sharper than 1, which will be the topic of future work.

######  Remark 2.

In Theorem 1 we assumed for simplicity that the stochastic gradients have
bounded covariances that are constant over time. In reality for the problem
above the covariance of the stochastic gradient in 5 will depend on the
current iterate $w_{k}$, but our choice can be justified. For example we can
add a projection to a bounded set $\|w_{k}\|<M$ in the algorithm, so we only
search over this restricted set of weights, resulting in bounded gradient
noise covariances.

######  Remark 3 (Analysis over mutiple iterations).

The above theoretical analysis is performed for one iteration of Alg. 1 (lines
5-9). As a result, at each iteration communication-efficiency is guaranteed.
After many iterations, the algorithm will converge to a neighborhood of the
desired set of weights $w$, i.e., the value function approximation. This
analysis will be explored in future work.

##  IV Practical scheme for communication-efficient reinforcement learning

Despite the above guarantee, implementing the theoretical communication scheme
in 9 would be practically impossible because it requires information that is
not known. Specifically it would require for every agent to know the Markov
Decision Process and the data distribution in order to compute the actual
performance gain. Since these are unknown, one approach is to estimate the
performance gain from the data. In particular, since the objective function is
quadratic, we can write the performance gain as

$\displaystyle
J\left(w_{k}-\varepsilon\hat{\nabla}_{i}J(w_{k})\right)-J(w_{k})=-\varepsilon\hat{\nabla}_{i}J(w_{k})^{T}\nabla
J(w_{k})$
$\displaystyle+\frac{1}{2}\varepsilon^{2}\hat{\nabla}_{i}J(w_{k})^{T}\nabla^{2}J(w_{k})\hat{\nabla}_{i}J(w_{k})$
(13)

This is a quadratic function of the stochastic gradient
$\hat{\nabla}_{i}J(w_{k})$. Then we can approximate the gradient and the
Hessian at each agent as

$\displaystyle\nabla J(w_{k})\approx\hat{\nabla}_{i}J(w_{k})$
$\displaystyle\nabla^{2}J(w_{k})\approx\frac{1}{T}\sum_{t=0}^{T}\phi(x^{t})\phi(x^{t})^{T}$
(14)

Hence, using the expression for the information gain in IV, we can approximate
the gain at agent $i=1,2$ as222Overall at each agent these computations
require $O(Tn)$ operations hence are scalable.

$\displaystyle
J\left(w_{k}-\varepsilon\hat{\nabla}_{i}J(w_{k})\right)-J(w_{k})\approx$
$\displaystyle-\hat{\nabla}_{i}J(w_{k})^{T}\left[I-\varepsilon\frac{1}{2}\frac{1}{T}\sum_{t=0}^{T}\phi(x^{t})\phi(x^{t})^{T}\right]\hat{\nabla}_{i}J(w_{k})^{T}$
(15)

It is important to emphasize that this is no longer a simple quadratic
function of the stochastic gradient but a more complicated function - we note
that the data appear both in the stochastic gradients as well as in the matrix
in the middle. This approximate value of the gain may take again positive or
negative values but it induces an approximation error/bias.

As a result, we can implement the communication decision in 9 with the
approximation in IV. In this case we no longer have the performance guarantee
in Theorem 1. In numerical evaluations however we see that despite the bias
this mechanism performs very well.

######  Remark 4.

Another intuitive approach to evaluate the informativeness of the data is to
assume that the performance gain IV is large when the stochastic gradient has
a large norm $\|\hat{\nabla}_{i}J(w_{k})\|$ at an agent. However, recent work
[15, 16] has demonstrated that this approach is not necessarily communication-
efficient. A different perspective is followed by [17]. When agents do not
update their gradients at the server, the server keeps a memory of past
received gradients and uses them for gradient descent in 6. The advantage of
the present approach is that it introduces an explicit communication-learning
tradeoff that can be controlled by the parameter $\lambda$. Technically, the
approach [17] is developed for policy gradient methods, while here the
approach is developed for value-function-based approaches.

##  V Numerical results

G |
---|---
Figure 2: Left: Grid example. Agents count the time it takes to reach the goal
G while there is 50% uncertainty in transitioning to the right at top row.
Right: Comparison between our communication approach in 9 requiring the model
to compute the performance gains versus estimating the gains by IV.

We consider first a grid exploration example (Fig. 2) which is a finite state
Markov Decision Process with state space $X$. An agent can move in four
directions subject to the boundary constraints, while at the top part of the
grid there is a 50% uncertainty in transitions to the right because of
disturbances. The objective function is the total undiscounted ($\gamma=1$)
time it takes to reach a desired goal location G. We collect measurements from
multiple agents following the policy that randomizes over all actions at each
state.

We perform one iteration of Algorithm 1 following II-A where the initial value
function is chosen randomly. In order to learn the exact value function we
take the basis functions/features to be the indicators
$\phi(1)=[1,0,\ldots,0]^{T},\phi(2)=[0,1,0,\ldots,0]^{T}$, etc in 2. We
suppose each agent has few data tuples $T=10$ in every iteration, as described
in Section II, chosen from a uniform distribution $d$ on this finite state
space, and we take the stepsize to be $\varepsilon=1$. We implement the
theoretical approach 9 and the practical approach using IV. We pick the
parameter $\rho$ to be close to its smallest value allowed by Assumption 3.
For varying values of the parameter $\lambda$ we empirically compute the
average communication rate 7, and the average final learning performance
$J(w_{N})$ as defined in 3. The achieved tradeoff between the two is shown in
Fig. 2. As a comparison, we also include the results when agents randomly
decide whether the transmit their gradients or not, leading to an inefficient
outcome.

For the theoretical algorithm 9, we observe that a very high communication
efficiency can be achieved, i.e., by transmitting only a fraction of the time
it is possible to find very good solutions to the value function approximation
problem, hence achieving a good communication-learning tradeoff. For the
practical approach using IV of course the learning loss is higher due to the
bias introduced, but we also clearly observe a very good tradeoff between all
agents communicating all the time versus scarce communications only when
necessary.

Figure 3: Left: Communication-Efficient Distributed Value Function
Approximation. Infrequent communication example is shown. Middle: More
frequent communication example is shown. Right: A larger number of agents
learns faster.

Then for a more complicated scenario we consider a continuous (uncountable)
state space problem $X={\mathbb{R}}^{2}$. State transitions are given by a
stochastic linear dynamical system $x_{+}=Ax+w$, with
$A=\left[\begin{array}[]{cc}0.8&-0.2\\\ 0.1&1\end{array}\right]$, where $w$ is
a zero-mean Gaussian noise variable with covariance $0.1$. We also consider a
quadratic cost $c(x)=\|x\|^{2}$ and a discount factor $\gamma=0.9$. We want to
perform one value iteration following II-A where the initial value function is
chosen randomly. We would like to approximate the updated value function per 2
as a linear combination of polynomial functions of the states with maximum
degree 2 – that is
$\phi(x)=[x_{1}^{2},x_{2}^{2},x_{1}x_{2},x_{1},x_{2},1]^{T}\in{\mathbb{R}}^{6}$
– and we are searching for a vector of weights $w\in{\mathbb{R}}^{6}$. We
suppose each agent has at every iteration $T=10^{3}$ data tuples, as described
in Section II, chosen from a uniform distribution $d$ on the space
$[0,1]^{2}$. We take the stepsize to be $\varepsilon=1$ and the parameter
$\rho=0.999$. As expected when learning value functions on continuous state
space, in this case we need many more iterations and a larger amount of data,
in the order of $10^{8}$ data tuples.

We implement the practical communication algorithm with IV. Fig. 3 shows the
evolution of weights for a large penalty $\lambda$ on communication rate. The
figure shows that at the beginning no communication takes place because not
very high informative gradients are found, while more communication takes
place as learning progresses. Fig. 3 shows the same setup with a smaller
penalty $\lambda$ on communication, and we observe higher communication rate
and faster learning of the weights. These observations verify the findings of
Theorem 1. Finally Fig. 3 shows the same setup but with a larger number of
agents, 10 instead of 2. We observe that learning happens faster, with almost
the same amount of average communication rate. This observation is not yet
studied theoretically here and will be explored in future work.

##  VI Concluding remarks

This paper examines the problem of solving reinforcement learning tasks over a
network. To exploit the informativeness of the data, the notion of performance
gain is explored and is shown numerically how this can be approximated from
the data without further model knowledge. The approach is supported
theoretically and numerically. Ongoing work explores the use of the approach
in more complex networks and reinforcement learning algorithms.

Within this proof for brevity we denote the stochastic gradients and the
performance gains as

$g_{k}^{i}:=\hat{\nabla}_{i}J(w_{k}),\qquad\lambda_{k}:=\frac{\lambda}{\rho^{N-k-1}N}$
(16)

respectively.

###  -A Proof of Theorem 1

###### Proof.

Note that by the dynamics in 6 we can write

$\displaystyle J(w_{k+1})$
$\displaystyle=(1-\alpha_{k}^{1})(1-\alpha_{k}^{2})J(w_{k})$
$\displaystyle+\alpha_{k}^{1}(1-\alpha_{k}^{2})J(w_{k}-\varepsilon g_{k}^{1})$
$\displaystyle+(1-\alpha_{k}^{1})\alpha_{k}^{2}J(w_{k}-\varepsilon g_{k}^{2})$
$\displaystyle+\alpha_{k}^{1}\alpha_{k}^{2}J(w_{k}-\varepsilon/2g_{k}^{1}-\varepsilon/2g_{k}^{2}),$
(17)

depending on each of the four cases. Then due to the convexity of the problem
we have for the last case the bound

$J(w_{k}-\varepsilon/2g_{k}^{1}-\varepsilon/2g_{k}^{2})\leq
1/2J(w_{k}-\varepsilon g_{k}^{1})+1/2J(w_{k}-\varepsilon g_{k}^{2}).$ (18)

Substituting this bound in -A and after a rearrangement of terms we get

$\displaystyle J(w_{k+1})$
$\displaystyle\leq\frac{1}{2}(1-\alpha_{k}^{2})\Big{[}(1-\alpha_{k}^{1})J(w_{k})+\alpha_{k}^{1}J(w_{k}-\varepsilon
g_{k}^{1})\Big{]}$ $\displaystyle+\frac{1}{2}\alpha_{k}^{1}J(w_{k}-\varepsilon
g_{k}^{1})$
$\displaystyle+\frac{1}{2}(1-\alpha_{k}^{1})\Big{[}(1-\alpha_{k}^{2})J(w_{k})+\alpha_{k}^{2}J(w_{k}-\varepsilon
g_{k}^{2})\Big{]}$ $\displaystyle+\frac{1}{2}\alpha_{k}^{2}J(w_{k}-\varepsilon
g_{k}^{2})$ (19)

Then we have for agent 1

$\frac{1}{2}\lambda_{k}\alpha_{k}^{1}\leq\frac{1}{2}\lambda_{k}(1-\alpha_{k}^{2})\alpha_{k}^{1}+\frac{1}{2}\lambda_{k}\alpha_{k}^{1}$
(20)

and similarly for agent 2. Adding these with -A we get

$\displaystyle\frac{1}{2}\lambda_{k}(\alpha_{k}^{1}+\alpha_{k}^{2})+J(w_{k+1})$
$\displaystyle\leq\frac{1}{2}(1-\alpha_{k}^{2})\Big{[}\lambda_{k}\alpha_{k}^{1}+(1-\alpha_{k}^{1})J(w_{k})+\alpha_{k}^{1}J(w_{k}-\varepsilon
g_{k}^{1})\Big{]}$
$\displaystyle+\frac{1}{2}\alpha_{k}^{1}[\lambda_{k}+J(w_{k}-\varepsilon
g_{k}^{1})]$
$\displaystyle+\frac{1}{2}(1-\alpha_{k}^{1})\Big{[}\lambda_{k}\alpha_{k}^{2}+(1-\alpha_{k}^{2})J(w_{k})+\alpha_{k}^{2}J(w_{k}-\varepsilon
g_{k}^{2})\Big{]}$
$\displaystyle+\frac{1}{2}\alpha_{k}^{2}[\lambda_{k}+J(w_{k}-\varepsilon
g_{k}^{2})]$ (21)

Then the terms in the brackets can be bounded. Note that due to the choice in
9 the following inequality holds for all times (technically it holds almost
surely as all the variables involved are random variables)

$\lambda_{k}\alpha_{k}+(1-\alpha_{k}^{i})J(w_{k})+\alpha_{k}^{i}J(w_{k}-\varepsilon
g_{k}^{i})\leq\lambda_{k}+J(w_{k}-\varepsilon g_{k}^{i}).$ (22)

This can be easily verified by examining the two cases $\alpha_{k}^{i}=0$ or
$1$ separately. Substituting this inequality for agents $i=1,2$ in -A we get

$\displaystyle\frac{1}{2}\lambda_{k}(\alpha_{k}^{1}+\alpha_{k}^{2})+J(w_{k+1})$
(23)
$\displaystyle\leq\frac{1}{2}(1-\alpha_{k}^{2})\Big{[}\lambda_{k}+J(w_{k}-\varepsilon
g_{k}^{1})\Big{]}+\frac{1}{2}\alpha_{k}^{1}[\lambda_{k}+J(w_{k}-\varepsilon
g_{k}^{1})]$
$\displaystyle+\frac{1}{2}(1-\alpha_{k}^{1})\Big{[}\lambda_{k}+J(w_{k}-\varepsilon
g_{k}^{2})\Big{]}+\frac{1}{2}\alpha_{k}^{2}[\lambda_{k}+J(w_{k}-\varepsilon
g_{k}^{2})]$

which after rearranging terms gives

$\displaystyle\frac{1}{2}\lambda_{k}(\alpha_{k}^{1}+\alpha_{k}^{2})+J(w_{k+1})$
(24)
$\displaystyle\leq\lambda_{k}+\frac{1}{2}(1-\alpha_{k}^{2})J(w_{k}-\varepsilon
g_{k}^{1})+\frac{1}{2}\alpha_{k}^{1}J(w_{k}-\varepsilon g_{k}^{1})$
$\displaystyle+\frac{1}{2}(1-\alpha_{k}^{1})J(w_{k}-\varepsilon
g_{k}^{2})+\frac{1}{2}\alpha_{k}^{2}J(w_{k}-\varepsilon g_{k}^{2})$ (25)

Taking expectation over the stochastic gradients $g_{k}^{1}$ and $g_{k}^{2}$,
conditioned on the current iterate $w_{k}$, and using the symmetry of the
problem with respect to agents $i=1,2$ we get that

$\displaystyle\mathbb{E}[\frac{1}{2}\lambda_{k}(\alpha_{k}^{1}+\alpha_{k}^{2})+J(w_{k+1}){\,\big{|}\,}w_{k}]\leq\lambda_{k}+$
(26)
$\displaystyle\mathbb{E}[1-\alpha_{k}^{i}{\,\big{|}\,}w_{k}]\mathbb{E}[J(w_{k}-\varepsilon
g_{k}^{i}){\,\big{|}\,}w_{k}]+\mathbb{E}[\alpha_{k}^{i}J(w_{k}-\varepsilon
g_{k}^{i}){\,\big{|}\,}w_{k}]$

Then we have the following key fact, which is shown separately in Appendix -B,

$\mathbb{E}[\alpha_{k}^{i}J(w_{k}-\varepsilon
g_{k}^{i}){\,\big{|}\,}w_{k}]\leq\mathbb{E}[\alpha_{k}^{i}{\,\big{|}\,}w_{k}]\;\mathbb{E}[J(w_{k}-\varepsilon
g_{k}^{i}){\,\big{|}\,}w_{k}]$ (27)

Substituting this bound in 26, we get

$\displaystyle\mathbb{E}[\frac{1}{2}\lambda_{k}(\alpha_{k}^{1}+\alpha_{k}^{2})+J(w_{k+1}){\,\big{|}\,}w_{k}]$
$\displaystyle\leq\lambda_{k}+\mathbb{E}[J(w_{k}-\varepsilon
g_{k}^{i}){\,\big{|}\,}w_{k}]$ (28)

Then given the fact that the function $J(w)$ in 3 is quadratic, i.e., can be
written in the form

$J(w)=(w-w^{*})^{T}\mathbb{E}_{d}\phi(w-w^{*})+J(w^{*})$ (29)

where we denoted $\Phi:=\mathbb{E}_{d}\phi(x)\phi(x)^{T}$. From the property
of the stochastic gradient that the mean is unbiased
$\mathbb{E}g_{k}^{i}=\nabla_{w}J(w_{k})=2\phi(w-w^{*})$ with a constant
variance $G$, we get that

$\displaystyle\mathbb{E}[J(w_{k}-\varepsilon g_{k}^{i}){\,\big{|}\,}w_{k}]=$
$\displaystyle\mathbb{E}[(w_{k}-\varepsilon
g_{k}^{i}-w^{*})\Phi(w_{k}-\varepsilon g_{k}^{i}-w^{*})]+J(w^{*})$
$\displaystyle=(w_{k}-w^{*})^{T}(I-2\varepsilon\Phi)^{T}\Phi(I-2\varepsilon\Phi)(w_{k}-w^{*})$
$\displaystyle+\varepsilon^{2}\text{Tr}(\Phi G)+J(w^{*})$ (30)

Then by Assumption 3 we can bound

$\displaystyle\mathbb{E}[J(w_{k}-\varepsilon g_{k})$
$\displaystyle{\,\big{|}\,}w_{k}]\leq\rho
J(w_{k})+\varepsilon^{2}\text{Tr}(\Phi G)+(1-\rho)J(w^{*})$ (31)

Substituting this in 28 we get,

$\displaystyle\mathbb{E}[\lambda_{k}\frac{\alpha_{k}^{1}+\alpha_{k}^{2}}{2}+J(w_{k+1}){\,\big{|}\,}w_{k}]\leq\lambda_{k}+\rho
J(w_{k})$ (32) $\displaystyle+\varepsilon^{2}\text{Tr}(\Phi
G)+(1-\rho)J(w^{*})$ (33)

Then for time-varying parameter $\lambda_{k}=\frac{\lambda}{\rho^{N-k-1}N}$ we
get

$\displaystyle\mathbb{E}[\lambda\frac{\alpha_{k}^{1}+\alpha_{k}^{2}}{2N}+\rho^{N-k-1}J(w_{k+1}){\,\big{|}\,}w_{k}]\leq\frac{\lambda}{N}+\rho^{N-k}J(w_{k})$
(34)
$\displaystyle+\rho^{N-k-1}\varepsilon^{2}\text{Tr}(\Sigma_{x}G)+\rho^{N-k-1}(1-\rho)J(w^{*})$
(35)

Taking expectation on both sides with respect to the variable $w_{k}$,
iterating over time $k=0,\ldots,N-1$, summing up, and removing the canceling
terms on both sides, we get

$\displaystyle\mathbb{E}\left[\lambda\sum_{k=0}^{N-1}\frac{\alpha_{k}^{1}+\alpha_{k}^{2}}{2N}+J(w_{N})\right]\leq\lambda+\rho^{N}J(w_{0})$
(36)
$\displaystyle+\frac{1-\rho^{N}}{1-\rho}\left[\varepsilon^{2}\text{Tr}(\Phi
G)+(1-\rho)J(w^{*})\right]$ (37)

and complete the desired result 1. ∎

###  -B Proof of 27

Within this proof we drop the iteration index $k$. Let us denote by $F(g)$ the
distribution of the stochastic gradient $g:=\hat{\nabla}J(w_{k})$ at any
agent. Then we can rewrite 27 as

$\int\alpha(g)J(w-\varepsilon g)dF(g)\leq\int\alpha(g)dF(g)\int
J(w-\varepsilon g)dF(g)$ (38)

However, by definition of the communication rule 9 we have that $\alpha(g)=1$
only when $J(w-\varepsilon g)\leq J(w)-\lambda$ and zero otherwise. Let us
define this set of values $S=\\{g\in{\mathbb{R}}^{n}:J(w-\varepsilon g)\leq
J(w)-\lambda\\}$, which is allowed to be an empty set too. Then 27 is
equivalent to

$\displaystyle\int_{S}J(w-\varepsilon g)dF(g)\leq$
$\displaystyle\int_{S}dF(g)\left[\int_{S}J(w-\varepsilon
g)dF(g)+\int_{S^{c}}J(w-\varepsilon g)dF(g)\right]$ (39)

which is equivalent to

$\displaystyle\int_{S^{c}}dF(g)\int_{S}J(w-\varepsilon
g)dF(g)\leq\int_{S}dF(g)\int_{S^{c}}J(w-\varepsilon g)dF(g)$ (40)

We can bound the left hand side because we can bound $J(w-\varepsilon g)$
point wise on the set $S$ as

$\displaystyle\int_{S^{c}}dF(g)\int_{S}J(w-\varepsilon
g)dF(g)\leq\int_{S^{c}}dF(g)\int_{S}dF(g)\;[J(w)-\lambda]$ (41)

Further we can bound the right hand side of 40 as

$\displaystyle\int_{S}dF(g)\int_{S^{c}}J(w-\varepsilon
g)dF(g)\geq\int_{S}dF(g)\int_{S^{c}}dF(g)\;[J(w)-\lambda]$ (42)

Combining 41 and 42 we verify 40 and conclude the proof.

## References

  * [1] S. Chinchali, A. Sharma, J. Harrison, A. Elhafsi, D. Kang, E. Pergament, E. Cidon, S. Katti, and M. Pavone, “Network offloading policies for cloud robotics: a learning-based approach,” Autonomous Robots, pp. 1–16, 2021\.
  * [2] R. Lowe, Y. Wu, A. Tamar, J. Harb, P. Abbeel, and I. Mordatch, “Multi-agent actor-critic for mixed cooperative-competitive environments,” in Proceedings of the 31st International Conference on Neural Information Processing Systems, pp. 6382–6393, 2017.
  * [3] G. Qu, A. Wierman, and N. Li, “Scalable reinforcement learning of localized policies for multi-agent networked systems,” in Learning for Dynamics and Control, pp. 256–266, PMLR, 2020.
  * [4] S. Fattahi, N. Matni, and S. Sojoudi, “Efficient learning of distributed linear-quadratic control policies,” SIAM Journal on Control and Optimization, vol. 58, no. 5, pp. 2927–2951, 2020.
  * [5] K. Zhang, Z. Yang, H. Liu, T. Zhang, and T. Basar, “Fully decentralized multi-agent reinforcement learning with networked agents,” in International Conference on Machine Learning, pp. 5872–5881, PMLR, 2018.
  * [6] Y. Zhang and M. M. Zavlanos, “Distributed off-policy actor-critic reinforcement learning with policy consensus,” in 2019 IEEE 58th Conference on Decision and Control (CDC), pp. 4674–4679, IEEE, 2019.
  * [7] L. Cassano, K. Yuan, and A. H. Sayed, “Multi-agent fully decentralized value function learning with linear convergence rates,” IEEE Transactions on Automatic Control, 2020.
  * [8] T. T. Doan, S. T. Maguluri, and J. Romberg, “Finite-time performance of distributed temporal-difference learning with linear function approximation,” SIAM Journal on Mathematics of Data Science, vol. 3, no. 1, pp. 298–320, 2021.
  * [9] E. Tolstaya, F. Gama, J. Paulos, G. Pappas, V. Kumar, and A. Ribeiro, “Learning decentralized controllers for robot swarms with graph neural networks,” in Conference on Robot Learning, pp. 671–682, PMLR, 2020.
  * [10] J. Konečnỳ, H. B. McMahan, F. X. Yu, P. Richtárik, A. T. Suresh, and D. Bacon, “Federated learning: Strategies for improving communication efficiency,” arXiv preprint arXiv:1610.05492, 2016.
  * [11] T. Chen, G. Giannakis, T. Sun, and W. Yin, “Lag: Lazily aggregated gradient for communication-efficient distributed learning,” in Advances in Neural Information Processing Systems, pp. 5050–5060, 2018.
  * [12] A. Reisizadeh, A. Mokhtari, H. Hassani, A. Jadbabaie, and R. Pedarsani, “Fedpaq: A communication-efficient federated learning method with periodic averaging and quantization,” in International Conference on Artificial Intelligence and Statistics, pp. 2021–2031, 2020.
  * [13] H. H. Yang, Z. Liu, T. Q. Quek, and H. V. Poor, “Scheduling policies for federated learning in wireless networks,” IEEE Transactions on Communications, 2019.
  * [14] M. M. Amiri, D. Gündüz, S. R. Kulkarni, and H. V. Poor, “Update aware device scheduling for federated learning at the wireless edge,” in 2020 IEEE International Symposium on Information Theory (ISIT), pp. 2598–2603, IEEE, 2020.
  * [15] K. Gatsis, “Adaptive scheduling for machine learning tasks over networks,” in American Control Conference (ACC), 2021.
  * [16] K. Gatsis, “Linear regression over networks with communication guarantees,” in 3rd Annual Learning for Dynamics & Control Conference, 2021.
  * [17] T. Chen, K. Zhang, G. B. Giannakis, and T. Basar, “Communication-efficient policy gradient methods for distributed reinforcement learning,” IEEE Transactions on Control of Network Systems, 2021.
  * [18] D. J. Ornia and M. Mazo Jr, “Event-based communication in multi-agent distributed q-learning,” arXiv preprint arXiv:2109.01417, 2021.
  * [19] A. Mitra, H. Hassani, and G. Pappas, “Robust federated best-arm identification in multi-armed bandits,” arXiv preprint arXiv:2109.05700, 2021.
  * [20] M. Agarwal, B. Ganguly, and V. Aggarwal, “Communication efficient parallel reinforcement learning,” arXiv preprint arXiv:2102.10740, 2021.
  * [21] M. Eisen, M. M. Rashid, K. Gatsis, D. Cavalcanti, N. Himayat, and A. Ribeiro, “Control aware radio resource allocation in low latency wireless control systems,” IEEE Internet of Things Journal, vol. 6, no. 5, pp. 7878–7890, 2019.
  * [22] M. H. Mamduhi, D. Maity, J. S. Baras, and K. H. Johansson, “A cross-layer optimal co-design of control and networking in time-sensitive cyber-physical systems,” IEEE Control Systems Letters, vol. 5, no. 3, pp. 917–922, 2020\.
  * [23] F. Solowjow, D. Baumann, J. Garcke, and S. Trimpe, “Event-triggered learning for resource-efficient networked control,” in 2018 Annual American Control Conference (ACC), pp. 6506–6512, 2018.
  * [24] S. Ghosh and V. Gupta, “Eventgrad: Event-triggered communication in parallel stochastic gradient descent,” in 2020 IEEE/ACM Workshop on Machine Learning in High Performance Computing Environments (MLHPC) and Workshop on Artificial Intelligence and Machine Learning for Scientific Applications (AI4S), pp. 1–8, IEEE, 2020.
  * [25] M. Vaquero and J. Cortes, “Convergence-rate-matching discretization of accelerated optimization flows through opportunistic state-triggered control,” Advances in Neural Information Processing Systems, vol. 32, pp. 9770–9779, 2019.
  * [26] S. Magnússon, H. Shokri-Ghadikolaei, and N. Li, “On maintaining linear convergence of distributed learning and optimization under limited communication,” IEEE Transactions on Signal Processing, vol. 68, pp. 6101–6116, 2020.
  * [27] S. Magnússon, C. Enyioha, N. Li, C. Fischione, and V. Tarokh, “Convergence of limited communication gradient methods,” IEEE Transactions on Automatic Control, vol. 63, no. 5, pp. 1356–1371, 2017.
  * [28] S. Khirirat, S. Magnússon, A. Aytekin, and M. Johansson, “A flexible framework for communication-efficient machine learning,” in Proceedings of the AAAI Conference on Artificial Intelligence, vol. 35, pp. 8101–8109, 2021\.
  * [29] S. Levine, P. Pastor, A. Krizhevsky, J. Ibarz, and D. Quillen, “Learning hand-eye coordination for robotic grasping with deep learning and large-scale data collection,” The International Journal of Robotics Research, vol. 37, no. 4-5, pp. 421–436, 2018.
  * [30] D. P. Bertsekas, Dynamic programming and optimal control.  Athena scientific Belmont, MA, 2012.
  * [31] R. S. Sutton and A. G. Barto, Reinforcement learning: An introduction.  MIT press, 2018.
  * [32] M. Riedmiller, “Neural fitted q iteration–first experiences with a data efficient neural reinforcement learning method,” in European Conference on Machine Learning, pp. 317–328, Springer, 2005.
  * [33] V. Mnih, K. Kavukcuoglu, D. Silver, A. A. Rusu, J. Veness, M. G. Bellemare, A. Graves, M. Riedmiller, A. K. Fidjeland, G. Ostrovski, et al., “Human-level control through deep reinforcement learning,” nature, vol. 518, no. 7540, pp. 529–533, 2015.