fault tolerance
✓ | ✗ | Many | Model | ✗ | ✓
[139] | 2019 |  | RaspBerry Pi
---
STM32H7
Many | ✓ | ✗ | ✗ | Per-layer | Many | Data | ✗ | ✗
DADS [159] | 2019 |  | RaspBerry Pi 3
---
model B
1 | ✗ | ✗ | ✓ | Per-layer | Many | ✗ | ✗ | ✓
| COLT-OPE
---
[164]
2019 | ✗ | 1 | ✗ | ✗ | ✗ | Per-layer | Many | ✗ | Early exit | ✓
EDDL [177] | 2019 | Fog nodes | Many | ✓ | ✗ | ✗ |  | Per-layer
---
Per-segment
Many | Model |  | Sparsification
---
Early exit
✗
[154] | 2019 |  | GPU
---
GTX1080
1 | ✗ | ✗ | ✓ | Per-layer | 1 | ✗ | ✗ | ✓
[143] | 2019 | ✗ | 7 | ✓ | ✗ | ✗ |  | Per-layer
---
Per-segment
Many | Model | ✗ | ✗
| deepFogGuard
---
[168]
2019 | ✗ | Many | ✗ | ✗ | ✗ | Per-layer | Many | ✗ | ✗ | ✗
| 2steps-pruning
---
[158]
2019 | ✗ | 2 | ✗ | ✗ | ✗ | Per-layer | 1 | ✗ | pruning | ✗
| JointDNN
---
[162]
2019 | jetson tx2 | 1 | ✗ | ✗ | ✗ | Per-layer | 1 | ✗ | ✗ | ✓
AAIoT [170] | 2019 |  | Raspberry Pi,
---
Mobile PC,
Desktop PC,
Server
Many | ✓ | ✗ | ✗ | Per-layer | Many | ✗ | ✗ | ✗
MWWP [182] | 2020 | ✗ | Many | ✗ | health care | ✓ | Per-layer | Many | Data | ✗ | ✓
[183] | 2020 | Raspberry Pi | Many | ✓ |  | multi-view
---
object
detection
✗ | Per-segment | Many | Model | Compression | ✗
| CONVENE
---
[175]
2020 | ✗ | 1 | ✗ |  | Parallel data
---
sharing on
antennas
✗ | Per-segment | Many | Model | ✗ | ✓
DINA [169] | 2020 | ✗ | Many | ✗ | ✗ | ✗ | Per-segment | Many | Both | ✗ | ✓
[184] | 2020 | ✗ | Many | ✓ |  | Intelligent
---
Connected
Vehicles
✓ | ✗ | Many | ✗ | ✗ | ✗
[166] | 2020 | ✗ | 1 | ✗ | ✗ | ✗ | Per- layer | 1 | ✗ | Compression | ✗
[165] | 2020 | Huawei | 1 | ✗ |  | augmented
---
reality
in 5G
✓ | Per-layer | 2 | Data | Early-exit | ✓
[142] | 2020 | Raspberry Pi 3 | Many | ✓ |  | Visual based
---
applications
✗ | Per-segment | Many | Both | ✗ | ✗
| Deep Wear
---
[171]
2020 | Android wear | 2 | ✓ |  | Wearable
---
devices
✓ | Per-layer | 1 | ✗ | Compression | ✓
[140] | 2021 | Cloudlet | Many | ✓ | 5 G | ✓ | Per-layer | Many | Data | ✗ | ✓
| DistPrivacy
---
[185]
2021 |  | Raspberry Pi
---
STM32H7
LG Nexus 5
Many | ✓ | Data privacy | ✓ | Per-segment | Many | Both | ✗ | ✓

###  Use cases

The DNN distribution is applied in multiple AI-governed use cases, including
healthcare [182], object detection [183], and intelligent connected vehicles
[184]. In this section, we review the literature of two applications that
impose extra constraints to the system, namely data privacy and the
distribution on moving robots, which presents challenges in managing the
battery life, the connection with other participants and the dynamic model
selection to enhance the accuracy of the data captured in harsh environments.

####  IV-C1 Data privacy

The data captured by end-devices and sent to remote servers (e.g., from
cameras or sensors to cloud servers) may contain sensitive information such as
camera images, GPS coordinates of critical targets, or vital signs of
patients. Exposing these data has become a big security concern for the deep
learning community. This issue is even more concerning when the data is
collected from a small geographical area (e.g., edge computing) involving a
set of limited and cooperating users. In fact, if an attacker reveals some
data (even public or slightly sensitive), a DL classifier can be trained to
automatically infer the private data of a known community. These attacks,
posing severe privacy threats, are called inference attacks that analyze
trivial or available data to illegitimately acquire knowledge about more
robust information without accessing it, by only capturing their statistical
correlations. An example of a popular inference attack is the Cambridge
Analytica scandal in 2016, where public data of Facebook users were exploited
to predict their private attributes (e.g., political view and location). Some
well-known inference attacks are summarized in Table VII.

TABLE VII: Examples of inference attacks. Inference attacks | Exposed data | Sensitive data
---|---|---
| Side-channel attacks
---
[186]
| Processing time,
---
power consumption.
| Cryptographic
---
keys
| Location inference
---
attacks [187]
| smartphones’ sensor
---
data.
Location
| Feature inference
---
attacks [188]
| Prediction results,
---
partial features of the
DNN model.
DNN structure
| Membership inference
---
attacks [189]
| confidence level
---
of classes,
gradients.
| membership of
---
a sample to a
dataset.
| attribute inference
---
attacks [190]
| social data, likes,
---
friends.
| Gender, ages,
---
preferences.

Edge computing naturally enhances privacy of the sensitive information by
minimizing the data transfer to the cloud through the public internet.
However, additional privacy techniques should be adopted to further protect
the data from eavesdroppers. In this context, in addition to its ability to
allow the pervasive deployment of neural networks, the DNN splitting was also
used for privacy purposes. Meaning, by partitioning the model, partially
processed data is sent to the untrusted party instead of transmitting raw
data. In fact, in contrast to the training data that belongs to a specific
dataset and generally follows a statistical distribution, the inference
samples are random and harder to be reverted. Furthermore, the model
parameters are independent from the input data, which makes the inference
process reveal less information about the sample [88]. While preserving
privacy, the inevitable challenge of DNN partitioning that remains valid, is
selecting the splitting point that preserves the latency requirements of the
system.

TABLE VIII: Comparison between privacy-aware distribution strategies.
(H: High, M: Medium, L: Low). | Privacy-aware
---
strategy
| Privacy
---
level
| Accuracy
---
preserving
| DNN
---
re-training
| Compatibility
---
with IoT and DNNs
| Partitioning
---
strategy
| Communication
---
overhead
| Computation
---
overhead on
source-device
| Deep split [88]
---
H | ✓ | ✗ | ✓ | per-layer | L | H
| Feature extraction
---
[191, 192]
L | ✗ | ✗ | ✓ | per-layer | L | M
| Noise addition
---
[193, 194, 195]
M | ✗ | ✓ | ✗ | per-layer | M | H
| Cryptography [196]
---
H | ✗ | ✓ | ✗ | per-layer | M | H
| Privacy-aware
---
partitioning [185]
M | ✓ | ✗ | ✓ |  | Filter
---
splitting
H | L

Authors in [191] proposed to extract the features sufficient and necessary to
conduct the classification from the original image or from one of the layers’
outputs using an encoder and transmit these data to the centralized server for
inference. This approach prevents the exposure of irrelevant information to
the untrusted party that may use it for unwanted inferences. Nevertheless
offloading only extracted features contributes to minimizing the transmission
overhead, this work focused only on the privacy perspective. The work in [192]
also proposed feature extraction for data privacy, while achieving a trade-off
between on-device computation, the size of transmitted data, and security
constraints. In fact, selecting the split layer from where the data will be
extracted intrinsically presents a security compromise. Particularly, as we go
deeper in the DNN network, the features become more task specific and the
irrelevant data that can involve sensitive information are mitigated [197].
Hence, if the split is performed in a deep layer, the privacy is more robust
and the transmission overhead is lower. However, a higher processing load is
imposed on the source device. The latter work [192], along with the work in
[88], advised to perform deep partition in case the source device has enough
computational capacity. If the source device is resource-constrained, the
model should be partitioned in the shallow layers, although most of the output
features are not related to the main task. Authors in [192] proposed a
solution based on Siamese fine-tuning [198] and dimensionality reduction to
manipulate the intermediate data and send only the primary measures without
any irrelevant information. In addition to enhancing privacy, this mechanism
contributes to reducing the communication overhead between the end-device and
the remote server.

However, to this end, the arms race between attacks and defenses for DNN
models has come to a forefront, as the amount of extracted features can be
sufficient for adversary approaches to recover the original image. Whereas,
less shared features may also result in low classification accuracy. The works
in [88, 199, 200] proposed adversarial attacks to predict the inference input
data (or the trained model), using only available features from shared outputs
between participants. Authors in [88] focused particularly on the privacy
threats presented by the DNN distribution; and accordingly, designed a white-
box attack assuming that the structure of the trained model is known and the
intermediate data can be inverted through a regularized Maximum Likelihood
Estimation (rMSE). Additionally, a black-box attack is also proposed, where
the malicious participant only has knowledge about his segment and attempts to
design an inverse DNN network to map the received features to the targeted
input and recover the original data. Authors demonstrated that reversing the
original data is possible, when the neural system is distributed into layers.
Numerous countermeasures have been considered to strengthen the robustness of
deep networks, including adding noise to the intermediate data to obfuscate
it, differential privacy, and cryptographic techniques that train the model on
encrypted samples.

Adding noise to the intermediate data is adopted in [193]. In this paper, the
authors proposed to perform a simple data transformation in the source-device
to extract relevant features and add noise. Next, these features extracted
from shallow layers are sent to the cloud to complete the inference. To
maintain a high classification accuracy, the neural network is re-trained with
a dataset containing noisy samples. However, adding noise to the intermediate
data costs the system additional energy consumption and computational
overhead. Therefore, the splitting should be done at a layer where the output
size is minimal. Though, the latter work did not describe the partition
strategy. The Shredder approach [194] resolved this dilemma by considering the
computation overhead during the noise injection process. The idea is to
conduct an offline machine learning training to find the noise distribution
that strikes a balance between privacy (i.e., information loss) and accuracy
drop. In this way, the DNN model does not require retraining with the noisy
data and the network can be cut at any point to apply directly the noise
distribution. The partitioning decision is based on the communication and
computation cost. A higher privacy level and lower communication overhead are
guaranteed, when the split is performed at deep layers; however, the
allocation at the end-device becomes less scalable. Adding noise or extracting
task-specific data can be included under the umbrella of differential privacy,
which at a high level ensures that the model does not receive any information
about the private input data, while still presenting satisfactory
classification. The performance of differential privacy is assessed by a
privacy budget parameter $\epsilon$ that denotes the level of
distinguishability. Authors in [195] conducted theoretical analysis to
minimize $\epsilon$, while considering accuracy and the communication overhead
to offload the intermediate features among fog participants.

Cryptography is another technique that can be used to protect the distributed
inference. The main idea is to encrypt the input data and process it using a
model trained on encrypted dataset, in a way the intermediate data cannot be
used by a malicious participant. Little research, including [196],
investigated the encrypted DNN distribution, as this approach suffers from a
prohibitive computation and communication overhead that exacerbates the
complexity of the inference process, particularly when executed in resource-
constrained devices.

All the previous techniques applied additional tasks to secure the shared
data, e.g., feature extraction, adding noise, and encryption, which overloads
the pervasive devices with computational overhead. Different from previous
works, DistPrivacy [185] used the partitioning scheme to guarantee privacy of
the data. In fact, all the existing privacy-aware approaches adopted the per-
layer distribution of the DNN model. This partitioning strategy incurs an
intermediate shared information that can be reverted easily using adversarial
attacks. The main idea in [185] is to divide the data resulting from each
layer into small segments and distribute it to multiple IoT participants,
which contributes to hiding the proprieties of the original image and
preventing untrusted devices from recovering the data. Particularly, the
authors adopted the filter splitting strategy, in such a way that each device
computes a part of the feature maps. However, as stated in section IV-A, this
partitioning strategy results in large data transmission between participants.
Therefore, the authors formulated an optimization that establishes a trade-off
between privacy and communication overhead.

Fig. 20 illustrates different privacy-aware strategies for distributed
inference existing in the literature.

Figure 20: Privacy-aware distribution strategies.

Table VIII shows the performance of different privacy-aware distribution
strategies. We can see that choosing the adequate strategy depends on the
requirements of the pervasive system, as multiple trade-offs need to be
established, such as the security level and accuracy, or the computation and
communication loads.

####  IV-C2 Distribution on moving robots

Currently, robotic systems have been progressively converging to
computationally expensive AI networks for tasks like path planning and object
detection. However, resource-limited robots, such as low power UAVs, have
insufficient on-board power-battery or computational resources to scalably
execute the highly accurate neural networks.

In surveillance applications, the aim is to monitor specific objects or
identify threats within the target region. Moving devices are the most
suitable technology to provide information about the target object from
different angles, which makes the identification more accurate. These data-
generating devices are only responsible for collecting the data, while servers
with higher capacities generate the identification results. The traditional
wisdom resorts to cloud or edge servers to compute heavy tasks. However, due
to the harsh environments where robots move (e.g., military border zones,
forests, and offshore oil reserves), the communication with remote servers is
strongly affected by the weather. Also, the processing might be difficult or
even impossible because of the interference resulting from the UAV altitude or
the underground environment (e.g., high-rise building effect on path loss).
Furthermore, as surveillance devices send high-resolution images to cloud/edge
servers at each small interval of time and knowing that incidents rarely
occur, the large data volume transmitted by source units has become
problematic, particularly for such systems characterized by an unstable
bandwidth availability. Because of this tremendous amount of data obtained
during the robots mission, AI should be integrated within the design of the
devices. However, moving robots come with distinct features, often
understated, such as that communicating with the remote servers while moving
incurs unstable latency, more energy consumption, and potential loss of data.

Figure 21: A fire detection scenario with distributed DNN.

The work in [201, 202] examined the case of per-layer distribution with one
split point between one UAV and one MEC server (see Fig. 21). More
specifically, the authors proposed a framework for AI-based visual target
tracking system, where low-level layers of the DNN classifier are deployed in
the UAV device and high-level layers are assigned to the remote servers. The
classification can be performed using only the low-level layers, if the image
quality is good. Otherwise, the output of these layers should be further
processed in the MEC server, for higher accuracy. In this context, the authors
formulated a weighted-sum cost minimization problem for binary offloading and
partial offloading, while taking into consideration the error rate/accuracy,
the data quality, the communication bandwidth, and the computing capacity of
the MEC and the UAV. The offloading probability is derived for the binary
offloading and the offloading ratio (i.e., the segment of DNN to execute in
the MEC) is obtained for the partial offloading scheme. In this model, the
mobility of the UAVs (i.e., the distance between the UAV and the server) is
involved through the transmission data rate between the device and the MEC, as
presented in Eq. (6) in the previous section IV-A. Additionally, the distance
between the UAV and the target impacts the quality of the image and
consequently impacts the offloading decisions. In the proposed framework,
multiple trade-offs are experienced:

  * •

The accuracy is achieved at the expense of delay and transmitted data: if most
of the images have bad quality, the system is not able to accomplish low
average latency as on-board inference is not sufficient. For this reason,
different inferences should be extended wisely using the segment allocated in
the MEC, particularly if the environment is challenging such as bad weather or
when the target is highly dynamic.

  * •

A trade-off exists also between the accuracy and latency, and the position of
the UAVs: when the device is close to the target, high resolution images can
be taken, which allows obtaining good accuracy on-board and avoiding the data
offloading. Being close to the targets is not always possible, particularly in
harsh environments or when the surveillance should be hidden.

  * •

The battery life is increased at the expense of the inference latency: the
battery can be saved, if processing coefficient is decreased, which enlarges
the computation time of the classification.

  * •

The split point selection: if the intermediate data is smaller than the raw
data, the offloading is encouraged to enhance the accuracy.

An online solution of this offloading trade-off using reinforcement learning
is presented in [203].

The previous works adopted the per-layer wise with one split point and remote
collaboration approach. This strategy is more adequate for flying devices that
can enhance their link quality by approaching the MEC stations. However, for
ground robots, offloading segments of the inference to remote servers costs
the system a large transmission overhead and high energy consumption. Authors
in [204] studied the distribution of the DNN network among ground robots and
profiled the energy consumed for such tasks, when moving or being in idle
mode. Several conclusions are stated:

  * •

When the robot is idle, the DNN computation and offloading increase the power
consumption of the device by 50%.

  * •

If the device is moving, the DNN execution causes high spikes in power
consumption, which may limit the device to attain a high performance as this
variation incurs a frequent change of the power saving settings in the CPU.

  * •

Distributing the inference contributes to reducing the energy consumed per
device, even-though the total power consumption is higher. This is due to the
reduced computation and memory operations per device and the idle time
experienced after offloading the tasks.

Based on the energy study of moving robots, the authors proposed to distribute
the DNN model into smaller segments among multiple low-power robots to achieve
an equilibrium of performance in terms of energy and number of executed tasks
[137]. Still, the distribution of the model into small segments (e.g., filter
splitting) requires the intervention of a large number of robots that are
highly dependent, which is not realistic.

##  V Federated Learning for Distributed Training

Despite the great potential of deep learning in different applications, it
still has major challenges that need to be addressed. These challenges are
mainly due to the massive amount of data needed for training deep learning
models, which imposes severe communication overheads in both network design
and end-users. Moreover, the conventional way of transferring the acquired
data to a central server for training comes with many privacy concerns that
several applications may not tolerate. In this context, the need for
intelligent and on-device DL training has emerged. More specifically, instead
of moving the data from the users to a centralized data center, pervasive
data-sources engage the server to broadcast a pre-trained model to all of
them. Then, each participant deploys and personalizes this generic model by
training it on its own data locally. In this way, privacy is guaranteed as the
data is processed within the host. The on-device training has been widely used
in many applications[42], such as the medical field, assistance services, and
smart education. However, this no-round-trip training technique precludes the
end-devices to benefit from others’ experiences, which limits the performance
of the local models. To this end, Federated Learning (FL) has been advanced,
where end-users can fine-tune their learning models while preserving privacy
and local data processing. Then, these local models (i.e., model updates) are
aggregated and synchronized (averaged) at a centralized server, before being
sent back to the end-users. This process repeats several times (i.e.,
communication rounds) until reaching converge. Accordingly, each participant
builds a model from its local data and benefits from other experiences,
without violating privacy constraints. FL is proposed by Google researchers in
2016 [205], and since then, it has witnessed unprecedented growth in both
industry and academia.

For the sake of completeness, we present in this section an overview for this
emerging pervasive learning technique, i.e., Federated Learning. In
particular, we introduce the computation and communication models of the FL
techniques. Then, we present a brief summary of the related works in the
literature, while highlighting a use case that considers the application of FL
within UAV swarms. It is worth mentioning that the FL can be used for both
online and offline learning (i.e., the training can be performed on static
datasets at once, or continuously training on new data received by different
participants). In this paper, we focus on studying the communication models of
the pervasive FL, which are valid for offline and online learning; and for
this reason we chose not to include it under the umbrella of the online
learning section. Fig. 22 summarizes the main subsections presented in what
follows.

Figure 22: Outline of federated learning.

###  Profiling computation and communication models

Generally, the FL system is composed of two main entities, which are the data-
sources (i.e., owners of data or pervasive participants) and the centralized
server (i.e., model owner). Let $N$ denote the number of data-sources. Each
one of these devices has its own dataset $D_{i}$. This private data is used to
train the local model $m_{i}$, and then the local parameters are sent to the
centralized server. Next, the local models are collected and aggregated onto a
global model $m_{G}=\bigcup_{i=1}^{N}m_{i}$. The FL is different from training
in the remote server, where the distributed data are collected and aggregated
first, i.e., $D_{G}=\bigcup_{i=1}^{N}D_{i}$, and then one model $m$ is trained
centrally. We assume that data-sources are honest and submit their real data
or their true local models to the centralized server. Otherwise, control and
incentive techniques are used to guarantee the reliability of FL, including
[206].

Typically, the life cycle of FL is composed of multiple communication rounds
that are completed when the centralized model reaches a satisfactory accuracy.
Each round includes the following steps:

  * •

Initialization of FL: The centralized server fixes the training task, the data
shape, the initial model parameters, and the learning process (e.g., learning
rate). This initial model $m_{G}^{0}$ is broadcasted to the selected
participants

  * •

Training and updating the local models: Based on the current global model
$m_{G}^{t}$, each data-source $i$ utilizes its own data $D_{i}$ to update the
local model $m_{i}^{t}$. We note that $t$ presents the current round index.
Hence, at each step $t$, the goal of each participant is to find the optimal
parameters minimizing the loss function $L(m_{i}^{t})$ defined as:

$m_{i}^{t*}=argmin_{m_{i}^{t}}L(m_{i}^{t})$ (11)

Subsequently, the updated parameters of the local models are offloaded to the
server by all selected participants.

  * •

Global model aggregation: The received parameters are aggregated into one
global model $m_{G}^{t+1}$, which will be sent back in its turn to the data
owners. This process is repeated continuously, until reaching convergence. The
server goal is to minimize the global loss function presented as follows:

$L(m^{t}_{G})=\frac{1}{N}\sum\limits_{i=1}^{N}L(m^{t}_{i})$ (12)

The aggregation of the global model is the most important phase of FL. A
classical and straightforward aggregation technique, namely FedAvg, is
proposed by Google reference paper [205] and presented in Algorithm 1.

Algorithm 1 FederatedAveraging (FedAvg) [205]

1:Input: $N$: participants, $D_{i}$: dataset of the device $i$, $B$: local
mini-batches, $E$: number of local epochs, $T$: number of rounds, $\rho$:
learning rate, c: fraction of participants.

2:Output: Global model $m_{G}$.

3:Initialization of FL: initialize $m_{G}^{0}$

4:Global model aggregation:

5:for t=1…T do

6: $NP\leftarrow max(c.N,1)$

7: $P\leftarrow$ select random $NP$ participants

8: for $i\in P$ in parallel do

9: $m_{i}^{t+1}\leftarrow$ Local model update $(i,m_{G}^{t})$

10: end for

11:
$m_{G}^{t+1}=\sum\limits_{i=1}^{N}\frac{|D_{i}|}{\sum\limits_{j=1}^{N}|D_{j}|}m_{i}^{t+1}$
% Averaging aggregation

12:end for

13:Local model update (i,m):

14:$d\leftarrow$ split $D_{i}$ into batches of size $B$

15:for j=1..E do

16: for samples $b\in d$ do

17: $m\leftarrow m-\rho\Delta L(m,b)$ % $\Delta L$ is the gradient of $L$

18: end for

19:end for

Algorithm 1 summarizes the aforementioned steps, where the centralized server
tries to minimize the global loss function by averaging the aggregation
following the equation in line 11. The FL system is iterated continuously
until the convergence of the global loss function or reaching a desirable
accuracy. A major challenge in FL is the large communication and energy
overhead related to exchanging the models updates between different end-users,
and the centralized server [207, 208]. Such overheads depend on multiple
parameters, including the models’ updates size, the number of participating
users, the number of epochs per user, and the number of communication rounds
required to maintain the convergence. Particularly, the energy consumed by an
FL participant $i$ characterized by a frequency $f$, a local dataset $D_{i}$,
and a number of local epochs $E$, is given by [209, 210]:

$e^{c}_{i}=E\times(\phi\gamma|D_{i}|f^{2}),$ (13)

where $\phi$ is the number of CPU cycles required to compute one input
instance, and $\gamma$ is a constant related to the CPU. The latency required
to compute the local model can be expressed as:

$t^{c}_{i}=E\times(\frac{\phi|D_{i}|}{f}).$ (14)

From the equations (13) and (14), we can see that a trade-off exists between
the local training latency and the consumed energy. More specifically, for a
fixed accuracy determined by the number of local epochs and a fixed frequency,
the latency is accelerated depending on the size of the private data. If the
data size and the accuracy are fixed, increasing the CPU frequency can help to
minimize the local model computation. However, minimizing the latency comes at
the expense of energy consumption that increases to the square of the
operating frequency.

Figure 23: The FL architectures considered in the literature: (a) one-layer
FL, (b) edge-assisted FL.

The transmission time to share the model updates between the centralized
servers and different FL participants mainly depends on the channel quality,
the number of devices and the number of global rounds, illustrated as follows:

$t^{T}=T\times\sum\limits_{i=1}^{N}\frac{K}{\rho_{i}},$ (15)

where $K$ is the models’ parameters size shared with the server and $\rho$ is
the data rate of the participant $i$. On the other hand, the total energy
consumed during the federated learning process using the local transmit powers
$P_{i}$ is equal to:

$e^{T}=T\times\sum\limits_{i=1}^{N}\frac{KP_{i}}{\rho_{i}},$ (16)

From the above equations, we can see that the local iterations $E$ and the
global communication rounds $T$ are very important to optimize the energy,
computation, and communication costs. Particularly, for a relative local
accuracy $\theta_{l}$, $E$ can be expressed as follows [211]:

$E=\alpha\times log(\frac{1}{\theta_{l}}),$ (17)

where $\alpha$ is a parameter that depends on the dataset size and local sub-
problems. The upper bound on the number of global rounds to reach the targeted
accuracy $\theta_{G}$ can be presented as [211]:

$T=\frac{\zeta log(\frac{1}{\theta_{G}})}{1-\theta_{l}}.$ (18)

We note that $\zeta log(\frac{1}{\theta_{G}})$ is used instead of
$O(log(\frac{1}{\theta_{G}}))$, where $\zeta$ is a positive constant. From
equations (17) and (18), we can see that the computation cost depending on the
local iterations $E$ and the communication cost depending on the global rounds
$T$ are contradictory. It means, minimizing $E$ implies maximizing $T$ and
consequently increasing the convergence latency.

To summarize, FL pervasiveness aspects that are being tackled by different
studies, to reduce communication and energy overheads, may include:

  1. 1.

reducing communication frequency, i.e., number of communication rounds;

  2. 2.

reducing the number of local iterations;

  3. 3.

selecting minimum number of participating users in the training process;

  4. 4.

optimizing local devices operating frequencies;

  5. 5.

minimizing the entropy of the models updates by using lossy compression
schemes;

  6. 6.

using efficient encoding schemes in communicating models updates.

In what follows, we categorize different presented FL schemes in the
literature, based on the system architecture, namely one-layer FL and edge-
assisted FL. The former refers to user-cloud architecture, where different
users share their learning models with a cloud or centralized server for
aggregation, while the latter refers to user-edge-cloud architecture, where
edge nodes are leveraged to reduce communication overheads and accelerate FL
convergence (see Figure 23).

###  Resource management for Federated learning

####  V-B1 One-layer Federated Learning

The concept of FL was first proposed in [205] by Google, with its efficiency
demonstrated through experiments on different datasets. The presented model in
[205] considered a one-layer FL, where the users exchange their updated models
with a centralized server that aggregates and forms an updated global model
with a fixed frequency.

Afterward, several extensions have been proposed to the original FL. The
investigated problems/approaches in FL, considering one-layer architecture,
can be categorized into:

  * •

analyzing the convergence of distributed gradient descent and federated
learning algorithms from a theoretical perspective, and optimizing the
learning process given computation and communication resource budget [212,
213, 214, 215];

  * •

considering partial user participation for the FL aggregation process in a
resource-constrained environment while balancing between the model accuracy
and communication cost [216, 217, 218, 219];

  * •

developing communication-efficient techniques to reduce the amount of
exchanged data in FL communications by adopting various sparsification and
compression techniques [220, 221, 222].

The effect of non-Independent and Identically Distributed (non-IID) data on
the performance of FL has been studied in [212]. It has been shown,
theoretically and empirically, that highly skewed non-IID data (i.e., the
local data at different users are not identically distributed) can
significantly reduce the accuracy of the global learning model by up to
$55\%$. As a solution to enhance the training on non-IID data, the authors
proposed to share globally a small subset of data between all users. Combining
this data with the local data of each user turns it to be less biased or
skewed. However, exchanging data between different users is not always
feasible due to the privacy constraint and communication overhead of sharing
such data. In [213], the authors analyzed the convergence rate of FedAvg on
non-IID data for strongly convex and smooth problems. In [214], the authors
studied the adaptation of global aggregation frequency for FL, while
considering a fixed resource budget. Indeed, they analyzed the convergence
bound of gradient-descent based FL on non-IID data from a theoretical
perspective. Then, they used this convergence bound to build a control
algorithm that adapts the frequency of global aggregation in real-time to
minimize the learning loss under a fixed resource budget. A new FL algorithm,
named FEDL, is presented in [215]. This algorithm used a local surrogate
function that enables each user to solve its local problem approximately up to
a certain accuracy level. The authors presented the linear convergence rate of
FEDL as a function of the local accuracy and hyper-learning rate. Then, a
resource allocation problem over wireless networks was formulated, using FEDL,
to capture the trade-off between the training time of FEDL and user’s energy
consumption.

It is shown in [213] that the participation of all users in the FL process
enforces the central server to wait for stragglers, i.e., users who have low-
quality wireless links that can significantly slow down the FL process, which
turns the FL to be unrealistic. Thus, to mitigate the impact of stragglers,
the authors in [216] proposed a method to select a subset of users for the FL
synchronization (or aggregation) process in a resource-constrained
environment. They demonstrated the advantages of such a technique on improving
the FL learning speed. This work has been extended in [217], where a control
scheme is proposed, based on reinforcement learning, to accelerate the FL
process by actively selecting the best subset of users in each communication
round that can counterbalance the bias introduced by non-IID data. In [218], a
joint optimization framework for sample selection and user selection was
studied to keep a balance between the model accuracy and cost. However, the
distribution distance between different users was optimized in this framework
by adjusting the local batch size, which might lead to the under-utilization
of data in strongly skewed users. In [219], the problem of users selection to
minimize the FL training time was investigated on cell-free massive multiple-
input multiple-output (CFmMIMO) networks.

Alternatively, sparsification schemes have been studied to reduce the entropy
of the exchanged data (i.e., models’ updates) in FL communications. The
authors in [220] presented an approach that accelerates the distributed
stochastic gradient descent by exchanging sparse updates instead of dense
updates. Indeed, they fixed the sparsity rate by only communicating the
fraction of entries with the biggest magnitude for each gradient. In [221],
the authors proposed a sparse ternary compression scheme that was designed to
maintain the requirements of the FL environment. The proposed scheme
compressed both the upstream and downstream communications of FL leveraging
sparsification, ternarization, error accumulation, and optimal Golomb
encoding. This study demonstrated the effect of communications compression and
data distributions on the obtained performance. However, it neither considered
the wireless resources allocation nor the edge-assisted FL architecture. In
[222], the FedAvg scheme was adjusted to use a distributed form of Adam
optimization, along with the sparsification and quantization, in order to
propose a communication-efficient FedAvg.

####  V-B2 Edge-assisted Federated Learning

Few studies have been proposed so far to address the problem of non-IID data
in edge-assisted FL architecture. For instance, the authors in [223] extended
the work in [214] to analytically prove the convergence of the edge-assisted
federated averaging algorithm. This work was further extended in [224]
considering probabilistic users selection to avoid the impact of stragglers.
In [225], a self-balancing FL framework, along with two strategies to prevent
the bias of training caused by imbalanced data distribution, was proposed. The
first strategy aimed to, before training the model, perform data augmentation
in order to alleviate global imbalance. The second strategy exploited some
mediators (which can be considered as edge nodes) to reschedule the training
of the users based on the distribution distances between the mediators. In
[226], the effect of the skewed data in edge-assisted FL was studied and
compared to the centralized FL. Indeed, this work identified the major
parameters that affect the learning performance of edge-assisted FL. However,
this work ignored the resource allocation and wireless communications
constraints, such as bandwidth, energy consumption, and latency.

Table IX presents the taxonomy of the federated learning techniques described
in this section.

TABLE IX: Taxonomy of federated learning techniques. Refs | Year | FL devices | Architecture | Trained model | Aggregation algorithm | Dataset | Targeted metrics
---|---|---|---|---|---|---|---
[205] | 2017 |  | Mobile
---
devices
One-layer |  | \- 2NN
---
\- CNN
\- LSTM
FedAvg |  |  \- CIFAR-10 [227]
---
\- MNIST [228]
\- Accuracy vs rounds
[212] | 2018 |  | Mobile and
---
IoT devices
One-layer | \- CNN | Enhanced FedAvg |  | \- CIFAR-10
---
\- MNIST
\- KWS [229]
| \- Accuracy vs rounds
---
\- Shared data
\- Weight divergence
[213] | 2019 | End-users | One-layer | \- Logistic regression | FedAvg | \- MNIST |  | \- Global loss vs rounds
---
\- Rounds vs local epochs
[214] | 2019 | Edge nodes | One-layer |  | \- Squared-SVM
---
\- Linear regression,
\- K-means
\- CNN
FedAvg |  | \- MNIST
---
\- Energy [230]
\- User Knowledge
Modeling [231]
\- CIFAR-10
| \- Loss vs nodes
---
\- Accuracy vs nodes
[215] | 2019 | End-users | One-layer | ✗ |  | Non-weighted
---
averaging
✗ |  | \- Communication vs
---
computation time
\- Learning time vs energy
[216] | 2019 | End-users | One-layer | \- CNN | Averaging |  | \- CIFAR-10
---
\- Fashion-MNIST [232]
| \- Accuracy vs time
---
\- Number of participants
[217] | 2020 |  | Mobile
---
devices
One-layer | \- CNN |  | FedAvg with users seclection
---
Favor
| \- MNIST
---
\- Fashion-MNIST
\- CIFAR-10
-Accuracy vs rounds
[218] | 2020 | End-users | One-layer |  | \- MLP
---
\- CNN
| FedAvg
---
\- MNIST | \- Accuracy vs rounds
[219] | 2020 |  | Mobile
---
devices
One-layer | ✗ | ✗ | ✗ |  | \- Transmission time
---
\- Loss
[221] | 2020 |  | Mobile
---
devices
One-layer |  | \- VGG11
---
\- CNN
\- LSTM
\- Logistic regression
| Weighted averaging with
---
Top-k sparsified communication
| \- CIFAR
---
\- KWS
\- MNIST
\- Fashion-MNIST
| \- Communication delay
---
\- Accuracy
[222] | 2020 |  | IoT
---
devices
One-layer |  | \- 2NN
---
\- CNN
| communication-efficient
---
FedAvg (CE-FedAvg)
| \- CIFAR-10
---
\- MNIST
| \- Uploaded data
---
\- communication rounds
\- convergence time
[233] | 2020 | UAVs | One-layer | ✗ | FedAvg | ✗ | \- Rounds vs bandwidth
[234] | 2020 | UAVs | One-layer | \- FCN | FedAvg |  CRAWDAD [235] |  | \- Accuracy vs rounds
---
\- local learning time
[236] | 2020 | UAVs | One-layer | \- CNN | FedAvg | \- MNIST | \- Utility of participants
[237] | 2020 | UAVs | One-layer |  | \- LSTM
---
\- GRU
\- AQNet [238]
FedAvg |  | \- Ground and aerial
---
Sensing Data collected
by authors
\- Energy consumption
[223] | 2020 | End-users | Edge-assisted | \- CNN | Hierarchical FedAvg |  | \- CIFAR-10
---
\- MNIST
| \- Accuracy vs epochs
---
\- Training time
\- Energy consumption
[224] | 2020 | End-users | Edge-assisted |  | \- FCN
---
\- LeNet-5
| Weighted averaging with
---
Effective Data Coverage (EDC)
| \- MNIST
---
\- Aerofoil [239]
| \- Accuracy vs rounds
---
\- Training time
\- Energy consumption
[225] | 2021 |  | Mobile
---
devices
Edge-assisted | \- CNN | FedAvg |  |  \- EMNIST [240]
---
\- CINIC-10 [241]
\- CIFAR-10
| \- Accuracy vs rounds
---
\- Accuracy vs epochs
\- Storage requirement
[226] | 2021 | End-users | Edge-assisted |  | \- FCN
---
\- CNN
FedAvg |  | \- MNIST
---
\- Fashion-MNIST
\- CIFAR-10
| \- Accuracy vs rounds
---
\- Accuracy vs edge
distance distribution
\- Speed

###  Use case: Learning in the sky

Figure 24: An example of FL applications in UAV-assisted environment.

Nowadays, deep learning has been widely used in Flying Ad-hoc Network (FANET).
Different tasks can be executed using DL techniques at UAV swarms, such as
coordinated trajectory planning [233] and jamming attack defense [234].
However, due to the related massive network communication overheads,
forwarding the generated large amount of data from the UAV swarm to a
centralized entity, e.g., ground base stations, makes implementing centralized
DL challenging. As a promising solution, FL was introduced within a UAV swarm
in several studies [233, 234, 236, 237] to avoid transferring raw data, while
forwarding only local trained models’ updates to the centralized entity.
Models aggregation and generation of a global FL model is the responsibility
of the centralized entity, who will also send this global model to the end-
user and all participants over the intra-swarm network (see Fig. 24).

In [233], the authors present a FL framework for the swarm of wirelessly
connected UAVs flying at the same altitude. The considered swarm includes a
leader UAV and a set of followers UAVs. It is assumed that each follower
collects data while flying and implements FL for executing inference tasks
such as trajectory planning and cooperative target recognition. Hence, each
follower exploits its gathered data to train its own learning model, then
forwarding its model’s updates to the leading UAV. All received models are
then aggregated at the leading UAV to generate a global FL model, that will be
used by the following UAVs in the next iteration. Interestingly, [233]
investigates the impact of wireless factors (such as fading, transmission
delay, and UAV antenna angle deviations) on the performance of FL within the
UAV swarms. The authors present the convergence analysis of FL while
highlighting the communication rounds needed to obtain FL convergence. Using
this analysis, a joint power allocation and scheduling optimization problem is
then formulated and solved for the UAV swarm network in order to minimize the
FL convergence time. The proposed problem considers the resource limitations
of UAVs in terms of: (1) the strict energy limitations due to the energy
consumed by learning, communications, and ﬂying during FL convergence; and (2)
delay constraints imposed by the control system that guarantees the stability
of the swarm.

###  Lessons learned

Despite the prompt development of diverse DL techniques in different areas,
they still impose a major challenge, which is: How can we efficiently leverage
the massive amount of data generated from pervasive IoT devices for training
DL models if these data cannot be shared/transferred to a centralized server?

  * •

FL has emerged as a promising privacy-preserving collaborative learning scheme
to tackle this issue by enabling multiple collaborators to jointly train their
deep learning models, using their local-acquired data, without the need of
revealing their data to a centralized server [221]. However, a major dilemma
in FL is the large communication overhead associated with transferring the
models’ updates. Typically, by following the main steps of FL protocol, every
node or collaborator has to send a full model update in every communication
round. Such update follows the same size of the trained model, which can be in
the range of gigabytes for densely-connected DL models [242]. Given that large
number of communication rounds may be needed to reach the FL convergence on
big datasets, the overall communication cost of FL can become unproductive or
even unfeasible. Thus, minimizing the communication overheads associated with
the FL process is still an open research area.

  * •

We also remark that despite the considerable presented studies that have
provided significant insights about different FL scenarios and user selection
schemes from the theoretical perspective, optimizing the performance and
wireless resources usage for edge-assisted FL is still missing. Most of the
existing schemes for FL suffer from slow convergence. Also, considering FL
schemes in highly dynamic networks, such as vehicular networks, or resource-
constraint environments, such as healthcare systems, is still challenging.

Figure 25: Outline of online learning.

##  VI Online learning

In this section, we discuss three prominent online learning formulations:
Multi-agent Reinforcement Learning (MARL), Multi-agent Bandit (MAB) problem,
and Active Learning (AL). The ”Multi-agent” prefix indicates the existence of
multiple collaborative agents 333Note that while competitive settings can also
be modeled, the focus of this section is on systems that aim to jointly
optimize an objective function with minimum resource utilization (pervasive AI
systems). Thus, competitive and zero-sum games will not be deeply surveyed.
that are aiming to optimize a specific criterion through learning from past
experience (i.e., past interactions). We note that MARL and bandits were
originally proposed to model a single agent interacting with the environment
and aiming to maximize its reward. However, in pervasive systems, where there
are numerous but resource-limited agents (i.e., devices), collaboration
becomes essential to leverage the potential of the collective experience of
these devices. Motivated by the prevalence of collaboration in pervasive
systems, we review in this section distributed MAB and MARL algorithms from a
resource utilization perspective. We also highlight that AL can be performed
both as an offline and online learning, although the latter is considered as
the edge of the AL technique. Thus, in this paper, we focus on the online
execution of AL, where the trained dataset is updated progressively in real-
time.

As has been the case throughout the paper, we are interested in the
performance/resource-management trade-offs. Specifically, we propose a
taxonomy based on the obtained performance with specific resource budgets
(e.g., communication rounds). Fig. 25 shows the taxonomy of the online
learning discussed in this section.

###  Multi-agent multi-arm bandit learning

In this section, we first provide technical definitions of the single-agent
bandit problem and then explain its multi-agent version.

####  VI-A1 Overview

Figure 26: The basic bandit problem: a set of actions corresponding to
different reward distributions.

The Bandit problem, introduced earlier in section III, is given in Algorithm
2, and visually illustrated in Fig. 26. Fundamentally, there exists a set of
actions $\mathcal{K}$ (10 actions in the figure), where each action $a$
results in a reward sampled from a distribution $\mathcal{D}_{a}$ (Gaussians
in the example illustrated in Fig. 26).

Algorithm 2 Basic bandit problem

1:The set of $K$ actions (arms) $\mathcal{K}$,

2:for each round $t\in[T]$:

3: Algorithm picks an action $a_{t}$

4: Environment returns a reward $r_{t}\sim\mathcal{D}_{a_{t}}$

The problem instance is fully specified by the time horizon $T$ and mean
reward vector (the vector of the expected reward for each action/arm)
$\bm{\mu}=u_{a},a\in\mathcal{K}$, where $u_{a}=\mathbb{E}[\mathcal{D}_{a}]$.
The optimal policy is simply choosing the action whose expected value is the
highest, i.e., $a_{*}=\mathop{\mathrm{arg\,max}}_{a}u_{a}$. However, as this
action is not known a priori ($\mathcal{D}_{a}$ is not known), it has to be
estimated online from samples. Thus, it is inevitable that some sub-optimal
actions will be picked, while building certainty on the optimal one. A
reasonable performance measure is the _Regret_ , which is defined as the
difference between the optimal policy’s cumulative rewards, and the cumulative
rewards achieved by a solution algorithm

$R_{T}=\underbrace{u_{*}\times T}_{\text{\shortstack{Optimal policy's\\\
cumulative rewards}}}-\underbrace{\sum_{t=1}^{T}u_{at}}_{\text{\shortstack{An
algorithm's cumulative\\\ rewards}}}$ (19)

Figure 27: Multi-agent bandits formulations: (a) Distributed Bandits: each
agent collaborates with others to identify the best action in the same
environment (b) Federated bandits: each agent collaborates with others to
identify the best global action using biased local samples. In this example,
the local environments were generated (e.g., sampled) from a global one.

In other words, the regret $R_{T}$ is the sum of _per-step regrets_. A per-
step regret at time step $t$ is simply the difference between the best
action’s expected reward $u_{*}$ and the expected reward of the action chosen
by an algorithm $u_{a,t}$ (i.e., $a$ is selected by the algorithm we are
following). Thus, it represents how much rewards are missed because the best
action is not found and has to be estimated from samples. Solution algorithms
typically prove sub-linear regret growth (i.e., this difference goes to zero
as time progresses. In this way, learning is achieved). The best achievable
regret bound for the described bandit problem was proven to be $O(logT)$
[243].

Several solution algorithms with optimal performance guarantees have been
proposed in the literature [243], which fall generally into two categories,
explore-then-commit and optimism-based algorithms. Explore-then-commit class,
such as successive elimination algorithm, acts in phases and eliminates arms
using increasingly sensitive hypothesis tests. On the other hand, the optimism
algorithm, such as Upper Confidence Bound (UCB) algorithm, builds confidence
for the reward of each action and selects the action with the highest upper
bound. The asymptotic performance of both classes is similar. Note that
performance guarantees are also classified into instance-dependent bound that
depends on the problem information such as the difference between the best and
second-best arms, and instance-independent regret (i.e., worst-case regret).
These algorithms are recently being extended to model pervasive systems though
two main MAB formulations: _distributed_ and _federated_ bandits, as shown in
Fig. 27.

In distributed bandits, agents aim to solve the same bandits instance (i.e.,
quickly discover the best action), represented by the action set and their
generating distributions. Meanwhile, in the federated bandit settings, agents
handle different bandits instances and utilize each others’ experiences to
solve them. While the terms used to describe the exact problem is sometimes
ambiguous in the literature (i.e., distributed, federated, and decentralized
were sometimes used interchangeably), in this work, we adopt the recent
convention on reserving the term federated for the case where each agent faces
a different (but related to others) problem instance, while keeping the term
distributed for the case where the instance is the same but the decision
making is distributed across other agents.

####  VI-A2 Distributed Bandits Formulations

In many bandit problem instances, it is appealing to employ more agents to
learn collaboratively and concurrently to speed up the learning process. In
the distributed bandit problem, there exists a set of agents $[M]$
collaborating to solve the _same_ bandit instance (the $K$ arms are the same).
These agents communicate according to some networking topologies. In many
contexts, the sequential decision-making problem at hand is distributed by
nature. For example, we can consider a recommender system deployed over
multiple servers in different locations. While every server aims to always
recommend the best item, it is intuitive to reuse each other’s experiences and
cut the time needed to learn individually. Furthermore, since their
communication may violate the latency constraints, it is desirable that this
collaboration and reuse of experience require minimum communication overhead.

While the classical single-agent bandit algorithm has been proposed since the
$~{}2002$, its multi-agent counterpart is much more recent, with new state-of-
the-art algorithms being currently proposed. The work in [244] initiated the
interest in the communication-regret trade-off. The authors established a non-
trivial bound on the regret, given an explicitly stated bound on the number of
exchanged messages. However, they focused on the full-information setting
assuming that the agents observe the rewards of all actions at each round, and
not only the one picked, which is the case in bandit settings. Nonetheless,
this work initiated the interest in studying the same trade-off under the
bandit settings. The authors of [245] considered the partial feedback (i.e.,
bandit settings) and presented an optimal trade-off between performance and
communication. This work did not consider regret as the performance criterion,
but rather assumed the less common “best arm identification” setup, where the
goal is to purely explore in order to eventually identify the best arm with
high probability after some number of rounds. The authors in [246] studied the
regret of distributed bandits with a gossiping-based P2P communication
specialized to their setup, where at every step, each agent communicates only
with two other agents randomly selected. [247] studied the regret under the
assumption that the reward obtained by each agent is observable by all its
neighbors. [248] proposed a collaborative UCB algorithm on a graph-network of
agents and studied the effect of the communication graph topology on the
regret bound. [249] improved this line of work as the approach requires less
global information about the communication graph by removing the graph
dependent factor multiplying the time horizon in the regret bound.

Other works go beyond merely studying the effect of the network topology on
the regret bound and explicitly accounting for the communication resources to
use. The authors in [250] deduced an upper bound on the number of needed
communicated bits, proving the ability to achieve the regret bound in [249]
with a finite number of communication bits. However, the interesting question,
particularly from the perspective of pervasive system design, is whether the
use of communication resources can also be bounded, i.e., can the order of
optimal regret bound be guaranteed with a maximum number of communicated bits
/ communicated messages ?

The work in [251] established the first logarithmic upper bound on the number
of communication rounds needed for an optimal regret bound. The authors
considered a complete graph network topology, wherein a set of agents are
initialized with a disjoint set of arms. As time progresses, a gossiping
protocol is used to spread the best performing arm with agents. The authors
showed that, with high probability, all agents will be aware of the best arm
while progressively communicating at less (halving) periods. The authors
generalized this work with a sequel formulation [252], which relaxes the
assumption of a complete graph, and introduces the option for agents to pull
information. However, this approach is still using the same gossiping style of
communication. According to [253], this dependence on pair-wise gossiping
communication results in a sub-optimal instance-independent regret bound. The
authors in [254] focused on the regret-communication trade-off in the
distributed bandit problem. The networking model utilizes a central node that
all agents communicate with. Initially, agents work independently to eliminate
bad arms. Then, they start communicating with the central node at the end of
each epoch, where epochs’ duration grows exponentially, leading to a
logarithmic bound on the number of needed messages.

TABLE X: Multi-agent stochastic bandit learning literature. Refs |  Problem Formulation |  Communication Model |  Communication Guarantee | Regret Guarantee | Method
---|---|---|---|---|---
P2P-$\epsilon$-Greedy [246] | DB | Two Neighbors on a graph | $O(T)$ | $O(T)$ | Gossiping arms estimates.
coop-UCB2 [248] | DB | Neighbors on a graph | $O(T)$ | $O(logT)$ |  A running Consensus on the estimates of arms total rewards.
UCB-Network [247] | DB |  Multiple (Graph and centralized) | $O(T)$ | $O(logT)$ |  Identifying and utilizing dominating sets in the network.
DDUCB [249] | DB | Neighbors on a graph | $O(T)$ |  $O(logT)$ (with improved constants) |  A running Consensus on the estimates of arms total rewards.
[251] | DB |  Single neighbors on a complete graph | $O(constant)$ | $O(logT)$ |  Gossiping among different local Poison clocks.
GosInE [252] | DB |  Neighbors on a complete graph | $\Omega(T)$ | $O(logT)+C_{G}$ |  Gossiping and information pulling.
DPE2 [250] | DB | Neighbors on a graph | $O(constant)$ | $O(logT)$ |  Leader-election to handle exploration (exploration is centralized).
DEMAB [254] | DB | Centralized coordinator | $O(logT)$ | $O(logT)$ |  Utilizing public randomness to divide arms among clients.
LCC-UCB [253] | DB |  Multiple (Graph and centralized) | $O(logT)$ | $O(logT)$ |  communicating after doubling-epochs with maintaing fixed.
[255] | FB | Neighbors on a graph | $O(logT)$ | $O(logT+C_{G})$ |  Selecting the best arm according to voting.
GossipUCB [256] | FB | Neighbors on a graph | $O(T)$ |  $O(max\\{logT,log_{C_{G}}N\\})$ |  Maintaining local belief that is updated through gossiping.
[257] | FB | Centralized coordinator | $O(logT)$ | $O(logT)$ |  Aggregating estimates through the controller until a fixed point of time.
[258] | FB | Centralized coordinator | $O(logT)$ | $O(logT)$ |  Mixed target learning objective based on local and global objectives.
[259] | FB | Neighbors on a graph | $O(T)$ | $O(logT)$ |  Agent use estimates of their neighbors weighted by a similarity metric.

The work in [253] presents a state of the art distributed bandit learning
algorithm. The authors proposed algorithms for both fully connected and
partially connected graphs (i.e., assuming that every agent can broadcast to
everyone and assuming that agents can communicate with a subset of the
others). Similar to elimination-based algorithms, the proposed algorithm
proceeds with epochs of doubling lengths, only communicating at the end of an
epoch, thus guaranteeing a logarithmic need for communication resources. The
communicated messages are only the ID of the action played most often.
Furthermore, the regret is proved to be optimal even in instance independent
problems, for reasonable values of the time horizon (i.e., $log(T)>2^{14}$).
During each epoch, agents maintain a set of arms that are recommended by other
agents at the end of previous epochs and implement a UCB algorithm among
these.

####  VI-A3 Federated Bandits Formulation

The federated bandit formulation, shown in Fig. 27 (b), is a recently emerging
framework akin to the federated learning framework discussed earlier. In this
formulation, there exists a set of agents, each one is facing a _different_
instance of the bandit (but the instances are related to each other). This is
different from the distributed bandit formulation discussed in the previous
sub-section, where a set of agents collaborate to solve the _same_ instance of
the multi-arms bandits. Recall that a bandit instance is determined by the
mean vector $\bm{\mu}$. Thus, in the federated bandit settings, the local
bandit instance is a _noisy_ and potentially _biased_ observation of the mean
vector. In addition, the collaboration is necessary, as even perfect local
learning algorithms might not perform adequately due to their biased
observations.

The setting of federated bandits is first proposed by [255] (although not
under the same term). The authors proposed an algorithm, where agents agree on
the best global arm, and they all play it at the beginning of each round. In
this way, communication is needed at the beginning of each round. Recently,
[256] studied this federated setting, where the global arm mean vector is the
average of the local ones. Although the authors did not propose a bound on the
number of messages needed to be exchanged, the communication model considered
a partially connected graph, where each agent communicates only with neighbors
but with focus on constrained communication resources. The algorithm contains
two main steps: First, each agent shares a set of local information with other
neighbors (the number of times an arm was sampled and its sampled mean) .
Second, a gossip update is performed, where each agent incorporates
information received from neighbors in updating its estimate of each arm’s
mean.

[258] presented a more general formulation, where the global mean vector is
not necessarily the average of the local ones. Instead, the local means are
themselves _samples_ from a distribution whose mean is unknown. The local
observation for each agent is, in turn, samples from the local distributions.
The communication model is similar to supervised federated learning, where
agents communicate periodically with an orchestrator that updates the
estimates of arms payoffs and instructs the agents on which arms to keep and
which to eliminate. Although the communication is periodic, the total number
of communication rounds is bounded (logarithmic with respect to the horizon
$T$). This is because the number of agents incorporated in the learning
process decays exponentially with time. Such an approach works since the
average of clients’ local means concentrates exponentially fast around that
global mean (a known result from probability concentration analyses).

A setting that is slightly different from the federated bandits was studied
in[259]. The difference is that although agents have similar yet not identical
local models, the reward for each agent is actually sampled from its local
distribution. Thus, each agent of them is trying to identify the best arm in
its local instance through using information from other ones on arms that are
similar. This is in contrast with other works presented here where the agents’
rewards are sampled from a _global_ distribution that they are collaboratively
trying to estimate from biased local observations.

Table X summarizes the works in MAB problems. It lists the problem
formulation: distributed Bandits (DB) or federated Bandits (FB), the
communication model (i.e., the network topology), the communication guarantee
(i.e., number of messages needed to achieve the performance), the regret
guarantee (i.e., the growth of the regret with respect to the time horizon),
and the method (i.e., the main principle behind the algorithms). $C_{G}$
donates a constant related to the communication graph or gossiping matrix.

####  VI-A4 Lessons Learned

  * •

Communication-cognizant Multi-agent Bandit formulations: Online-learning
systems need to account for the communication resources. Thus, recent works do
not only analyze regret but explicitly reason about the necessary
communication resources. This is manifested through two main observations.
First, the derived regret guarantees are always affected by the networking
topology (e.g., parameters representing the connectivity of a communication
graph, number of involved agents, or number of exchanged messages). Second,
accompanied by every regret guarantee, an upper bound on communication
resource usage is also provided (e.g., the maximum number of exchanged
messages or exchanged bits).

  * •

Towards the federation of the bandit framework: When the bandit instances
faced by each agent are local biased instances, the federated bandits
framework arises. In such situation, agents need to learn with the help of a
logically centralized controller, similar to supervised federated learning, in
order to estimate the true global instance and the true best action[258].
However, if agents are not interested in solving a hidden global instance but
rather only their own, they may reuse their peers’ experience and an instance-
similarity metric to help them solve their own instances [259].

###  Multi-agent reinforcement learning

This section presents an overview of Multi-agent Reinforcement Learning (MARL)
from a pervasive system perspective. We specifically focus on the
_communication-performance_ trade-off and classify previous works according to
their approach to handle this trade-off. We note that our perspective is
different from previous surveys (i.g., [260], [261]), which studied the
technical merits and demerits of the learning algorithms. Instead, we are
interested in the _systems_ aspects of the considered works. That is, what are
the communication topology and protocol used between agents and how do these
choices affect the performance (rewards obtained by all agents).

####  VI-B1 Overview

Figure 28: MARL Framework: multiple autonomous agents act on an environment
and observe (parts) of its state, and a, potentially different, reward signal.

Unlike MAB formulations, in reinforcement learning, we have a _state space_ ,
which is a set of all possible states (i.e., configuration) the environment
might be in, along with a _transition operator_ which describes the
distribution over the next states given the current state and performed
actions. Therefore, agents need to not only detect the best actions, which
maximize the reward (bandits objective) but also to account for the possible
next state, as it might be arbitrarily bad/good regardless of the current one.
Hence, in MARL, the collaborative agents aim to maximize the current and
_future_ expected sum of rewards.

MARL problems, visualized in Fig. 28, are often modeled as a Partially
Observable Markov Game (POMG)[262], which is a multi-agent extension for
Partially Observable Markov Decision Process (POMDP). POMGs are represented by
the tuple
$(\mathcal{N},\mathcal{S},\mathcal{A},\mathcal{O},\mathcal{T},\mathcal{R},\gamma)$,
where:

  * •

$\mathcal{N}$ is the set of all agents.

  * •

$s_{t}\in\mathcal{S}$ is a possible configuration of all the agents at time
$t$.

  * •

$a_{t}\in\mathcal{A}$ is a possible action vector for the agents, where
$\mathcal{A}=\mathcal{A}_{1}\times\mathcal{A}_{2}\times....\times\mathcal{A}_{N}$.

  * •

$o_{t}\in\mathcal{O}$ is a possible observation of the agents, where
$\mathcal{O}=\mathcal{O}_{1}\times\mathcal{O}_{2}\times....\times\mathcal{O}_{N}$.

  * •

$\mathcal{T}:\mathcal{O}\times\mathcal{A}\mapsto\mathcal{O}$ is the state
transition probability.

  * •

$\mathcal{R}$ is the set of rewards for all the agents
$r_{i}:\mathcal{O}\times\mathcal{A}\mapsto\mathbb{R}$.

  * •

$\gamma$ is the reward discount factor.

Each agent aims to find a policy $\pi_{n}$ that maximizes its own reward. In
cooperative scenarios, the policy aims at maximizing the total reward. If the
rewards are not the same for all agents, the framework is referred as mixed
Decentralized-POMDP. When the rewards are similar for all agents (i.e.,
$r_{n}=r\quad\forall n\in\mathcal{N}$), the POMG is collaborative. In the
following, we discuss algorithms that might work on one or both settings. The
main focus will be, on the communication aspects (i.e., topology and cost) of
MARL algorithms.

There exist results on the hardness of solving the POMG under several
settings. We can cite the case of a tabular representation of the spaces and
the cases where function approximation is used (linear or nonlinear). The main
solution approaches are policy gradient, value-based methods [263]. Policy
gradient methods parametrize agents’ policies within a class and utilize
gradient descent to optimize an objective function (i.e., reward obtained by
the policy). Value-based methods aim to generalize the famous Q-learning
algorithm to the multi-agent settings, either through making each agent learn
its own Q-function and treating others as a part of a non-stationary
environment , or through learning a global Q-function.

The optimization in policy gradient methods is done on the objective function:
$J(\mathbf{\theta}\doteq v_{\pi_{\mathbb{\theta}}}(s_{0}))$, which is the cost
of starting from the intitial state $s_{0}$, and following the parametrized
policy $\pi_{\mathbf{\theta}}$ thereafter. The gradient of this function can
be written as:

$(G_{t}-b(S_{t}))\frac{\nabla\pi(A_{t}|S_{t},\mathbb{\theta}_{t})}{\pi(A_{t}|S_{t},\mathbb{\theta}_{t})}.$
(20)

As shown in the policy gradient algorithm [263], $b$ is any function of the
state, referred to as the baseline. If it is the zero function, the resulting
equation represents the “reinforce” algorithm. Another popular option is the
value function of the state. If this state value function is updated through
bootstrapping, the resulting method is called Actor-critic. Thus, Actor-critic
methods are policy gradients that use the state value function as a baseline
($b(s)=V(s)$) and update this function through bootstrapping. Readers may
refer to [264] for more details and comparison between these approaches. As
will be clarified next, each work tunes different parts of these main solution
approaches according to the application.

####  VI-B2 Centralized training and Decentralized Execution (CTDE)

The Centralized Training and Decentralized Execution (CTDE) approach is
originally proposed in [265]. This approach leverages the assumption that, in
most application scenarios, the initial training is done on centralized
simulators, where agents can communicate with each other with no communication
cost. This phase is denoted as centralized training. Then, at deployment,
agents are assumed not to communicate at all, or conduct limited communication
with each other, and they rely on their “experience” at the training phase to
actually execute their collaborative policies.

##### Communication only at training

The advantage of such an approach is that it does not require communication
between agents upon deployment and thus incurs no communication cost. However,
this comes at the cost of losing adaptability, which is the major motivation
behind online learning. Such loss might occur in case of a major shift in the
environment model between the training and deployment, where the learned
coordinated policies are no longer performant, and new coordination is needed.
The main workaround is to monitor the agents’ performance and re-initiating
the centralized training phase to learn new coordinated policies whenever
needed.

This approach has been popularized by recent methods such as VDN [266], QMIX
[267], and QTRAN [268]. These works adopt _value function factorization_
technique, where factorizations of the global value function in terms of
individual (i.e., depending only on local observations) value function are
learned during centralized training. Then, the global function (i.e., neural
network) can be discarded at execution time, and each individual agent
utilizes only the local function. When each agent acts greedily according to
its local network, the global optimality can still be guaranteed since, at the
training phase, these local networks were trained according to gradient
signals with respect to the global reward.

Another approach to solving POMG is actor-critic. The CTDE version of actor-
critic approaches is represented by learning a centralized critic, which
evaluates the global action, and decentralized policy network, which outputs
an action based only on local observation. During training, the actor-critic
networks are jointly learned, and hence the global critic “guides” the
training of the actors. Then, at execution, the global critic may be
discarded, and only actors can be used. The works in [269] present a deep
deterministic policy gradient method that follows the described approach,
where each agent learns a centralized critic and decentralized actor.
Similarly, [270] follows the same approach, but all agents learn the same
critic. Multiple other variations are done on the same DDPG algorithm aiming
to either enhance performance [271] through incorporating an attention-
mechanism, or limit the use of communication resources (limited budget on the
number of messages used, or a message is (a part of) an agent’s state). [272].

TABLE XI: Communication-Cognizent Multi-Agent Reinforcement Learning literature. Refs | Framework |  Learning algorithm |  Communication scheme |  Communication decision
---|---|---|---|---
VDN [266], QMIX [267], QTRAN [268] | CTDE | Value-based | NA |  Always during training, None at execution.
MADDPG [269], COMA[270] | CTDE | Actor-critic-based | NA |  Always during training, None at execution.
[273] IMAC | CTDE with learned comm. | Policy gradient |  Learned source and destination |  At every step (limited size)
[274] ATOC | CTDE with learned comm. | Actor-critic based |  Gated communication with neighbors |  When network topology changes.
[275] IC3Net | CTDE with learned comm. | Policy gradient |  Gated communication with neighbors |  Communicate when necessary, possibly many messages per round.
[276] ACML | CTDE with learned comm. | Actor-critic based |  Gated communication with neighbors |  Communicate when necessary, respecting a limited bandwidth.
[277] | Fully decentralized | Value-based | Indirect | No message passing.
[278] | Fully decentralized | actor-critic-based | With neighbors | At every step.
[279] | Fully decentralized | actor-critic-based | With neighbors | At every step (limited size).
[280] | Fully decentralized | Policy gradient |  Broadcast to all through central controller | At every step.

##### Learned communication

An important line of work within the MARL community is the study of learned
communication between agents. In these settings, agents are allowed to send
arbitrary bits through a communication channel to their peers in order to
convey useful information for collaboration. These agents need to learn _what_
to send, and _how_ to interpret the received messages so that they inform each
other of action selection. Thus, the agents are effectively learning
communication protocols, which is a difficult task [281].

While the learned communication can be trained centrally and executed in a
decentralized fashion, agents can still communicate at the execution phase
through a limited bandwidth channel. Hence, we distinguish this setting from
the works discussed in the previous subsection. Yet, similar approaches can be
followed. For example, discarding the critic in execution (sometime used
interchangeably with the term CTDE) but still maintaining the learned
communication [276] and parameter sharing and gradient pushing in [281], where
in execution, these messages are discretized.

The authors in [282] aimed to learn to schedule communication between agents
in a wireless environment and focused only on collision avoidance mechanism in
the wireless environment. In [273], information theoretic approach was used to
compress the content of the message. In addition, source and destination are
also learned through a scheduler. On the other hand, a popular line of work
concentrated on designing so-called _gating mechanism_ techniques in order to
accomplish the efficiency of the learned communication protocols. In this line
of work, agents train a gating network, which generates a binary action to
specify whether the agent should communicate with others or not at a given
time step, limiting the number of communicated bits/messages needed to realize
a certain desirable behavior. [274] investigates the adaptability of these
communication protocols and demonstrates the importance of communicating only
with selected groups. Specifically, agents cannot distinguish messages that
are particularly important to them (i.e., have implications on their actions)
from the messages of all other agents. Thus, they introduce an attention
scheme within each agent where an attention unit receives encoded local
observation and action intention of the agent to decide whether a
communication with others in its observable field is needed. The communication
group dynamically changes and persists only when necessary.

The authors in [275] looked at communication at scale and proposed an
Individualized Controlled Continuous Communication Model (IC3Net), where
agents are trained according to their own rewards (hence the approach can work
for competitive scenarios also). Then, they demonstrated that their designed
gating mechanism allows agents to block their communication, which is useful
in competitive scenarios and reduces communication in cooperative scenarios by
opting out from sending unnecessary messages. However, the effect of the gate
on communication efficiency was not thoroughly studied, and the focus was
instead on the emerging behavior. The work in [276] presents the state-of-the-
art on efficient learned communication. The authors introduced Actor-Critic
Message Learner (ACML), wherein the gate adaptively prunes less beneficial
messages. To quantify the benefit of an action, Gated-ACML adopts a global
Q-value difference as well as a specially designed threshold. Then, it applies
the gating value to prune the messages, which do not hold value. The authors
showed that surprisingly, not only the communication-efficiency significantly
increases, but in specific scenarios, even the performance improves as a
result of well-tuned communication. The reason behind this is that, since the
communication protocol is learned, it is probable to hold redundant
information that agents do not decode successfully. The proposed gating
mechanism can also be integrated with several other learned communication
methods.

####  VI-B3 Fully Decentralized Agents

In fully decentralized reinforcement learning, there is no distinction between
training and testing environments. Thus, the communication model stays the
same throughout the agents’ interaction with the environment. Under these
settings, we recognize two extreme cases. First, agents do not communicate
with each other, and learn to coordinate solely through the obtained rewards.
In the case of no communication, the major challenge faced by the agents is
the non-stationarity of the environment. A non-stationary environment from the
perspective of the agents is when the distribution of the next states varies
for the same current state and action pairs. The fully decentralized DRL was
recently popularized by [277]. In [277], the authors proposed a 3-dimensional
reply buffer whose axes are the episode index, timestep index, and agent
index. It was illustrated that conditioning on data from that buffer helps
agents the perceived non-stationarity of the environment.

On the other extreme, agents can be modeled to be able to communicate at every
step. Specifically, the problem of graph networked agents is investigated in
[278]. In this paper, agents are connected via a time-varying and possibly
sparse communication graph. The policy of each agent takes actions that are
based on the local observation and the neighbors’ messages to maximize the
globally averaged return. The authors fully decentralized actor-critic
algorithms and provided convergence guarantees when the value functions are
approximated by linear functions. However, a possible disadvantage of this
algorithm is that the full parameter vector of the value function is required
to be transmitted at each step. This has been addressed in [279], where also
graph-networked agents are assumed, but each agent broadcasts only one
(scaled) entry of its estimate of parameters. This significantly reduces
communication cost (given that it occurs at every iteration). The paper also
does not assume a bidirectional communication matrix and deals with only
unidirectional ones, which is a more general formulation that appeals to more
applications. The decentralized actor-critic-based algorithm also solves the
distributed reinforcement learning problem for strongly connected graphs with
linear value function approximation.

[280] considered the communication efficiency in fully decentralized agents,
but with the assumption of a centralized controller. The paper utilizes policy
gradient solution methods, where the controller aggregates the gradients of
the agents to update the policy parameters. This process is akin to federated
learning clients selection. The authors propose a process to determine which
clients should communicate to the controller based on the amount of progress
in their local optimization. They also propose a methodology to quantify the
importance of local gradient (i.e., the local optimization progress) and then
only involve agents who are above a certain threshold. Following this
approach, the authors showed that the performance (i.e., cumulative reward) is
similar to the case where all clients are participating, with considerable
communication round savings.

Table XI summarises the works discussed above according to their communication
model and the approach in handling the communication-performance tradeoff. We
first identify the framework CTDE, CTDE with learned communication, or fully
decentralized) as well as the learning algorithm (value, policy gradient, or
actor-critic). Then, we list two important columns. First, the communication
scheme, which states _how_ agents communicate with each other. In CTDE, the
training is done in simulation. Thus, agents are logically centralized and do
not communicate. If no messages are passed between agents and their
collaboration is solely learned through rewards, then the communication scheme
is indirect. Otherwise, it is either (gated) with neighbors directly or
through a central controller. Lastly, the communication decision columns state
_when_ the communication is made, which can be at every step (with optimized
message size or not), or according to other conditions as detailed in the
discussion.

####  VI-B4 Lessons Learned

  * •

CTDE-a practical middle ground: CTDE algorithm leverages the fact that
training is often done in simulators, where there is no communication cost,
and agents may share experience tuples, network parameters, and observations
freely, in order to train policies that can be executed later on, based on
only local observations. This approach seems to model most of the pervasive
systems applications where agents do not need to start training while being
decentralized. In this framework, the actor-critic-based algorithms are more
popular, where a centralized critic network that uses the observations of all
agents guides the training of a decentralized policy network that uses only
the local observations. The critic network can be discarded at execution time,
enabling decentralized execution. The framework is emerging as a possible
alternative to the fully decentralized extremes, which either communicate at
every step or do not communicate at all and try to indirectly and
independently learn collaborative policies [269, 272].

  * •

Scheduling for efficient learned communication: In learned communication,
agents learn to encode and decode useful messages. In this area, gating
mechanisms are the main tools towards efficient communication [274, 275, 276].
In gate design, agents learn when to send and refrain from sending a message
by quantifying the benefit (i.e., reward) of actions following this
communication. More general _schedulers_ modules investigate the design of
communication module that learn to minimize the content of the messages as
well (i.e., compressing the communication messages) [273]. Overall, scheduling
mechanisms are being increasingly used in MARL settings with learned
communication, in order to face the limited bandwidth problems often
encountered in practical scenarios.

###  Active Learning (AL)

As far as online learning schemes have been tackled, AL has emerged as a
promising and effective concept. Herein, we first present a brief overview for
the concept of AL, then we discuss some recent applications of AL presented in
the literature.

####  VI-C1 Overview

The main idea behind AL is that an active learner is allowed to actively
select over time the most informative data to be added to its training dataset
in order to enhance its learning goals [283], [284]. Hence, in AL framework,
the training dataset is not static, which means that the training dataset and
learning model are progressively updated in order to continuously promote the
learning quality [285]. Specifically, the main steps of AL are: (1) acquiring
new data from the contiguous nodes; (2) picking out the most informative data
to append to the training dataset; (3) retraining the learning model using
newly-acquired data. Hence, the communication overheads associated with
different AL schemes will depend on:

  1. 1.

Type and amount of exchanged data between the contiguous nodes. We remark here
that contiguous nodes can exchange labels, features, or samples. Hence, based
on the type and amount of changed data there will be always a tradeoff between
enhancing the performance and decreasing communication overheads.

  2. 2.

Number of selecting nodes that will be considered in the AL process.

It is worth mentioning also that FL allows multiple nodes to cooperatively
train a global model without sharing their local data, which differs from AL
in many ways. In particular, FL seeks for obtaining a synchronization between
different cooperative nodes, in addition to the presence of a centralized node
(or server) to generate the global model. Thus, AL and FL are addressing
orthogonal problems – the former leverages the newly-acquired data from the
contiguous nodes to retrain its model, while the latter trains its model in a
distributed manner by sharing the model’s updates with the contiguous nodes
[286].

####  VI-C2 Applications of AL

Traditionally, AL algorithms depend on the presence of an accurate classifier
that generates the ground-truth labels for unlabeled data. However, this
assumption becomes hard to maintain in several real-time applications, such as
crowdsourcing applications and automated vehicles. Specifically, in
crowdsourcing, many sources are typically weak labelers, which may generate
noisy data, i.e., data that may be affected by errors due to low resolution
and age of information problems. However, most of the existing studies on AL
investigate the noisy data (or imperfect labels) effect on the binary
classification problems [287, 288], while few works consider the general
problem of multi-class or multi-labeled data [289, 290, 291].

One of the main problems in crowdsourcing is how to collect large amount of
labeled data with high quality, given that the labeling can be done by
volunteers or non-expert labelers. Hence, the process of acquiring large
amount of labeled data turned to be challenging, computationally demanding,
resource hungry, and often redundant. Moreover, crowdsourced data with cheap
labels comes with its own problems. Despite being labels cheap, it is still
expensive to handle the problem of noisy labels. Thus, when data/labelers are
not selected carefully, the acquired data may be very noisy [292, 293], due to
many reasons such as varying degrees of competence, labelers biases, and
disingenuous behavior, which significantly affects the performance of
supervised learning. Such challenges have encouraged the researcher to design
innovative schemes that can enhance the quality of the acquired data from
different labelers. For instance, [289] tackles the problem of demanding deep
learning techniques to large datasets by presenting an AL-based solution that
leverages multiple freely accessible crowdsourced geographic data to increase
datasets’ size. However, in order to effectively deal with the noisy labels
extracted from these data and avoid performance degradation, the authors have
proposed a customized loss function that integrates multiple datasets by
assigning different weights to the acquired data based on the estimated noise.
[291] enhances the performance of supervised learning with noisy labels in
crowdsourcing systems by introducing a simple quality metric and selecting the
$\epsilon$-optimal labeled data samples. The authors investigate the data
subset selection problem based on the Probably Approximately Correct (PAC)
learning model. Then, they consider the majority voting label integration
method and propose two data selection algorithms that optimally select a
subset of $k$ samples with high labelling quality. In [290], the authors
investigate the problem of imbalanced noisy data, where the acquired labeled
data are not uniformly distributed across different classes. The authors
therein aim to label training data given received noisy labels from diverse
sources. Then, they used their learning model to predict the labels for new
unlabeled data, and update their learning model until some conditions are met
(e.g., the performance of the learned model meets a predefined requirement, or
it cannot be improved any more). Specifically, for labeled data, they
implement a label integration and data selection scheme that considers data
uncertainty and class imbalance level, while classifying the unlabeled data
using the trained model before adding them to the training dataset. Hence, the
proposed framework presents two core procedures: label integration and sample
selection. In the label integration procedure, a Positive LAbel Threshold
(PLAT) algorithm is used to infer the correct label from the received noisy
labels of each sample in the training set. After that, three sample selection
schemes are proposed to enhance the learning performance. These schemes are
respectively based on the uncertainty derived from the received-noisy labels,
the uncertainty derived from the learned model, and the combination method.

A different application of AL is investigated in [285], where AL is exploited
for incremental face identification. Conventional incremental face recognition
approaches, such as incremental subspace approaches, have limited performance
on complex and large-scale environment. Typically, the performance may
drastically drop when the training data of face images is either noisy or
insufficient. Moreover, most of existing incremental methods suffer from noisy
data or outliers when updating the learning model. Hence, the authors in [285]
present an active self-paced learning framework, which combines: active
learning and Self-Paced Learning (SPL). The latter refers to a recently
developed learning approach that mimics the learning process of humans by
gradually adding to the training set the easy to more complex data, where easy
data being those with high classification confidence. In particular, this
study aims to solve the incremental face identification problem by building a
classifier that progressively selects and labels the most informative samples
in an active self-paced way, then adds them to the training set.

AL has been also considered in various applications of intelligent
transportation systems. For instance, the authors in [294] investigate the
vehicle type recognition problem, in which labeling a sufficient amount of
data in surveillance images is very time consuming. To tackle this problem,
this work leveraged fully labeled web data to decrease the required labeling
time of surveillance images using deep transfer learning. Then, the unlabeled
images with high uncertainty are selected to be queried in order to be added
later to the training set. Indeed, the cross-domain similarity metric is
linearly combined with the entropy in the objective function of the query
criteria to actively select the best samples. Ultimately, we highlight that
most of the presented studies so far consider in their AL framework specific
classifiers (or learning models), which cannot be easily used in other
learning models [295]. Accordingly, obtaining an optimal label integration and
data selection strategy that can be used with a generic multi-class
classification techniques is still worth further investigation.

###  Use Cases

####  VI-D1 MAB for recommender systems

Online learning systems are fundamental tools in recommender systems, which
are, in turn, a cornerstone in the development of current intelligent user
applications, from social media application feeds to content caching across
networks. Due to the recent growth in data generation, local geo-distributed
servers are often used to support applications that utilize recommender
systems. Furthermore, privacy concerns sometimes limit the ability of these
local servers to share data with other servers. In [258], the authors motivate
the use of federated bandits by explaining how they can model such a critical
use case. In the discussed example, a set of servers run a recommender system
for their prospective clients. The goal of each one is to recommend the most
popular content across all servers. However, due to latency constraints,
communication at every decision-making step is infeasible. Besides, sharing
individual samples of rewards violates privacy, as all servers will learn
about a particular user’s choice and preference. Due to these reasons, the
authors proposed and utilized a federated bandits algorithm (Fed-UCB) which
only communicates $logT$ times in a $T$ horizon to minimize recommendation
latency. At each round, only the sample _means_ are communicated, preserving a
certain level of privacy (additional improvements are also discussed).
Finally, the performance of the system is shown to be near-optimal; thus,
achieving the goal of recommending the best item across all servers while
meeting the privacy and communication constraints.

####  VI-D2 MARL for UAV-assisted networks

Figure 29: UAV-assisted networks: UAV agents are trained to deduce a
collaborative policies for providing compute/communication resources for on
ground equipment.

UAVs have provided new potentials for extending communication coverage and
even compute capabilities of devices in areas where full networking
infrastructure is not present. This is done through wireless communication
between UAV and on-ground equipment, enabling those equipment to extend their
connectivity and potentially offload tasks to a broader network relayed by the
UAV. The work in [296] aims at utilizing UAVs to provide intermittent
compute/communication resource support for user equipments (UEs) on the
ground. The benefits of such UAV-assisted scenarios are numerous, including
creating dynamic networking graphs without the need for full networking
infrastructure, which can be of extreme value in catastrophes response for
example. Nonetheless, the UAVs need to optimize their trajectory paths so that
they cover the widest areas with minimum movement (i.e., energy consumption)
and maximum utility (i.e., providing the resources to the UE that needs it the
most). However, such optimization is shown to be intractable. Thus, the
authors opted for learning-assisted (i.e., data-driven) methods. Since a
centralized training was possible in their tackled scenario is available, they
used a CTDE algorithm, specifically Multi-Agent DDPG (MADDPG). In MADDPG,
agents aim to jointly optimize the UE-load of each UAV while minimizing the
overall energy consumption experienced by UEs, that depends on the UAV’s
trajectory and offloading decisions. Following the MADDPG algorithm, the UAVs
observations were communicated among them to deduce the collaborative policy
at training. At execution, no message sharing was needed. This resulted in a
satisfactory performance due to the accurate simulator. However, as discussed
earlier, environments that are expected to change might necessitates the use
of other algorithms that maintain periodic, learned, or persistent
communication after deployment.

We note that the application of reinforcement learning in resource-constrained
environments (e,g., IoT devices), requiring the design of communication-aware
techniques, is still scarce. Most testing for these methods is done on
artificial testing environments like Open AI’s Particle environments [297], or
video games like StarCraft II [298], which is a typical practice in the RL
community since success in these environments is often indicative of broader
applicability.

####  VI-D3 AL for Connected Vehicles

Figure 30: AL for time-varying vehicular network.

Traditional machine learning models require massive, accurately labeled
datasets for training in order to ensure high classification accuracy for new
data as it arrives [299]. This assumption cannot be guaranteed in many real-
time applications, such as connected and autonomous vehicles. Indeed, vehicles
are typically weak labelers (i.e., data sources that generates label with low
classification confidence). Hence, they may acquire/generate noisy data, e.g.,
data generated by cameras in the presence of fog or rain. Also, in a highly
dynamic environment like vehicular network, not only the generated data by the
vehicles’ classifiers can have low classification accuracy, but also the data
received from neighboring vehicles may be prone to noise and communication
errors. Hence, the authors in [300] have tackled these challenges by proposing
a cooperative AL framework for connected vehicles. The main goal of this work
is two-fold: (1) selecting the optimal set of labelers, those considered to be
the most reliable ones; as well as (2) selecting a maximally diverse subset of
high quality data that are locally-generated and/or received from neighboring
vehicles to be used for updating the learning model at each vehicle.

In [300], the time-varying vehicular network shown in Figure 30 is considered.
It is assumed that each vehicle can communicate and exchange information only
with the neighboring vehicles that are located within its communication range.
For instance, the set
$\mathcal{N}_{v_{0}}(t)=\left\\{v_{j},v_{j+1},v_{j+2}\right\\}$ at time $t$
means that there are only three vehicles staying in the communication range of
vehicle $v_{0}$. Furthermore, this framework considers two types of data:
multiple-labeled online dataset and offline/historical labeled dataset. The
online dataset is considered as sequences of samples that arrive from
neighboring vehicles or generated at vehicle $v_{0}$ within time $T$ (i.e.,
refers to the period of time during which a vehicle $v_{0}$ is exposed to a
certain road view). At time $T$, vehicle $v_{0}$ receives a sequence of
training samples/labels that contains input features and associates with
multiple noisy labels generated from the vehicles sending data to $v_{0}$. The
presented framework in [300] includes five main stages, as described below:

  1. 1.

Offline Learning: Initially, each vehicle with its own offline/historical
training data generates an initial learning model with a certain accuracy
level.

  2. 2.

Online labeling: The vehicle starts to collect new information through its
local sensors or from neighboring vehicles. These information can be labels,
features, or samples, depending on the adopted operational mode.

  3. 3.

Label integration: After acquiring the new information, each vehicle obtains
an aggregated label for the received data using different proposed label
integration strategies.

  4. 4.

Labeler selection: After monitoring the behavior of the neighboring vehicles,
each vehicle selects a subset of high-quality labelers, based on their
reputation values that are estimated from the past interactions using
subjective logic model.

  5. 5.

Data selection and models update: Finally, each vehicle selects the maximally
diverse collection of high-quality samples to update its learning model.

The proposed AL framework in [300] depicts its efficiency for connected
automated vehicles, as follows: (1) it allows for increasing the amount of
acquired data at different vehicles during the training phase; (2) it accounts
for the labelers’ accuracy, data freshness, and data diversity while selecting
the optimal subset of labelers and data to be included in the training set;
(3) Using different real-world datasets, it could provide $5-10\%$ increase in
the classification accuracy compared to the state-of-the-art approaches that
consider random data selection, while enhancing the classification accuracy by
$6\%$ compared to random labelers selection approaches.

Figure 31: Future directions and open challenges.

##  VII Future directions and open challenges

In this section, we present a list of open challenges and issues facing the
pervasive AI systems, and we propose some promising ideas to mitigate these
issues. Specifically, we introduce the opportunities to integrate the
pervasive AI in emerging systems, and we suggest some future directions for
efficient distributed inference and enhanced federated learning algorithms.
Finally, we present some innovative ideas related to the new concepts of
online learning. Fig. 31 presents a brief of the proposed directions.

###  Deployment of Pervasive AI in emerging systems

####  VII-A1 Pervasive AI-as-a-service

While the 5G main goal is to provide high speed mobile services, the 6G
pledges to establish next-generation softwarization and improve the network
configurability in order to support pervasive AI services deployed on
ubiquitous devices. However, the research on 6G is still in its infancy, and
only the first steps are taken to conceptualize its design, study its
implementation, and plan for use cases. Toward this end, academia and industry
communities should pass from theoretical studies of AI distribution to real-
world deployment and standardization, aiming at instating the concept of
Pervasive AI-as-a-service (PAIaas). PAIaas allows the service operators and AI
developers to be more domain-specific and focus on enhancing users’ quality of
experience, instead of worrying about tasks distribution. Moreover, it permits
to systemize the mass-production and unify the interfaces to access the joint
software that gathers all participants and applications.

####  VII-A2 Incentive and trusty mechanism for distributed AI using
blockchain

The distribution of heavy and deep neural networks on ubiquitous and resource-
limited devices contributes to minimizing the latency of the AI task and
guarantees the security of the data. However, even though pervasive systems
are composed of computing units existing everywhere, anytime, and not
belonging necessarily to any operator, the distribution is based on the
assumption that pervasive devices are consenting to participate in the
collaborative system. In this context, several considerations should be
examined first: (1) The design of an incentive mechanism to motivate different
nodes to take over AI tasks and sacrifice their memory, energy, communication,
and computation resources to gain some rewards (e.g., monetary remuneration
and free access to services); (2) In addition to the security of the private
data to be processed by the pervasive devices, the security of the
participants’ information should be guaranteed (e.g., locations, identifiers,
and capacities). Recently, blockchain [301] has gained large popularity as a
decentralized dataset managing transaction records across distributed devices,
while ensuring trusty communication. Moreover, the aforementioned
incentivizing mechanism can also be handled by blockchain systems. More
specifically, all source devices and pervasive nodes have to first register to
the blockchain system to benefit from the distributed AI or to participate in
the computation. Then, data-generating devices request help to accomplish a
task and submit at the same time a transaction application to the blockchain
with a reward. Next, when the joining devices complete the offloaded tasks,
they return the results to the source device and validate the completion of
the transaction. Finally, the recorded participants are awarded according to
their contribution to the blockchain transaction. The edge-based blockchain
has a promising potential to prevent the security threats of transferring data
between heterogeneous, decentralized, and untrusted devices. However, this
approach is still in its infancy. Particularly, deploying it in resource-
constrained devices is challenging due to the huge energy and computation load
of blockchain mining [302].

####  VII-A3 Explainable AI (XAI)

The AI-based applications are increasingly involved in many fields, where the
decisions are very critical to lives and personal wellness, such as smart
health applications and autonomous drones used during wars. However, most of
the users do not have visibility on how the AI is making decisions. This lack
of explainability prevents us to fully trust the predictions generated by AI
systems. Finding reasons and logical explanations for decisions made by AI is
called Explainable AI (XAI) [16, 303, 304]. XAI is an emerging field that is
expected to answer some questions, including: Why are some predictions chosen,
and why others not? When does an AI model succeed in taking the right
decision, and when it fails?

Various techniques are used to explain the AI: (1) One of these techniques is
decomposability, which stands for the ability to describe each part of the
model, extract features of the output, and analyze them using clustering
methods. The pervasive AI system is the most adequate environment to empower
XAI by improving the ability to interpret, understand, and explain the
behavior of the model. More specifically, by distributing the inference, the
model becomes algorithmically transparent, and each segment can be interpreted
and clustered by its importance for the prediction. (2) Moreover, among the
most important directions supporting the XAI is model debugging. Debugging a
DNN allows to detect errors and understand their sources and their influence
on misleading the prediction. A distributed model produces fine-grained
outputs, that help to follow the inference process and localize the errors
before reaching the prediction layer. (3) A third direction to explain the AI
is the extraction of data samples that are highly correlated with the results
generated by the model. In fact, similarly to human behaviors when trying to
understand some processes, examples are analyzed to grasp the inner
correlation that is derived by the AI model. Federated learning is based on
clustering data entries and training local models. This technique permits us
to narrow the examples search and enables the detection of the most
influencing inputs on the model behavior. Research on XAI is still in its
infancy, and pervasive DNN computing looks like a promising environment to
track the AI process and interpret the results.

###  Efficient algorithms for pervasive inference

####  VII-B1 Online resource orchestration

The pervasive systems are characterized by an extremely dynamic environment,
where the available computing resources are volatile, and the load of requests
may follow some statistical distributions. More specifically, ubiquitous nodes
can join and leave the pervasive system randomly, which makes it hard to
estimate the available resources. Moreover, the load of requests depends on
the IoT application. For example, surveillance systems require frequent image
processing (e.g., face recognition and crowd monitoring) every small interval
of time. On the other hand, other applications, such as weather, air quality,
and pollution level estimation, have to gather a specific amount of data
before requesting the inference, which makes the load of requests lower.
Additionally, the quality of the collected data may affect the depth of the
adopted DL and consequently the computation requirements of the tasks. As an
example, capturing high quality images allows to have a good prediction using
smaller networks. In this scenario, early-exit techniques or squeezed models
can be adopted. Having such data quality depends on the source device (e.g.,
UAV, professional camera, mobile phone, etc.) and the dynamic of the targets
(e.g., fixed or moving).

Because of this network’s dynamics, the pervasive systems deploying
distributed inference need a well-designed online resource orchestration and
participants selection strategy to support the large number of AI services
with minimum latency. Meanwhile, heterogeneous and limited resources, and high
dimensional parameters should be taken into consideration. In section IV, we
have introduced existing theoretical approaches to split different DNN
networks and distribute the resultant segments into pervasive devices to
optimize pervasive computing. Nonetheless, most of them focused on how to
partition the model in order to maximize the data parallelism and minimize the
dependency between participants. Yet, there is no relevant work that deeply
studied the performance of DNN distribution and reported the bottleneck and
gain of such an approach in long-term online resource orchestration, with
different loads of requests and a dynamic behavior of participants and
sources. In other words, the model parallelism is not well investigated in the
literature, where sources can generate multiple requests at the same time and
offload them to neighboring devices. In this scenario, the critical decision
is to choose whether to process the same task from different requests while
minimizing the memory to store the filters’ weights or to compute sequential
tasks from the same request while reducing the transmission among
participants. Furthermore, the age-aware inference is an important factor that
can be foreseen in online model parallelization. In fact, some requests are
highly sensitive to delays and need to be processed timely, such as self-
driving cars, whereas others are less critical, including machine translation
and recommendation systems. Thus, prioritizing urgent tasks and assigning
better resources and intensive data parallelization to them is of high
importance. We believe that pervasive AI computing should focus more on the
online configuration to implement the above vision.

####  VII-B2 Privacy-aware distributed inference

Guaranteeing the privacy of the data shared between collaborative devices is
one of the main concerns of pervasive systems, since untrusted participants
may join the inference and observe critical information. Because of this
heterogeneity of ubiquitous devices, the trained models are subject to
malicious attacks, such as black-box and white-box risks, by which the
original inputs may be in jeopardy. In this case, privacy-aware mechanisms
should be enhanced to ensure the security of the distributed inference
process. Many efforts have been conducted in this context, such as noise
addition and cryptography. Even though these techniques succeeded in hiding
features of the data from untrusted devices, most of them suffer from
computation overhead and incompatibility with some end-devices or DNNs. More
specifically, noisy or encrypted data need to be re-trained to preserve the
accuracy of the prediction, and each input has to be obfuscated, which adds a
computation overhead. Moreover, encryption may not be applicable for all DNN
operations nor possible in some end-devices due to the crypto key management
requirements. A notable recent work [185] proposed to use the distribution for
data privacy, without applying any additional task requiring computation
overhead. In fact, per-segment splitting leads by design to assigning only
some features of the input data to participants. Authors, of this work,
applied filter partitioning and conducted empirical experiments to test the
efficiency of black-box attacks on different segments’ sizes (i.e., number of
feature maps per device). The lower the number of feature maps per device, the
higher the privacy. However, filter partitioning incurs high communication
load and dependency between devices. This study is still immature. Other
partitioning strategies (e.g., channel and spatial.) can be examined to
identify the optimal partitioning and distribution that guarantee satisfactory
privacy and minimum resource utilization per participant.

####  VII-B3 Trajectory optimization of moving robots for latency-aware
distributed inference

The usage of robots (e.g., UAVs) proved its efficiency to improve services in
critical and hard-reaching regions. Recently, moving robots have been used for
real-time image analysis, such as highway inspection, search and rescue
operations, and border surveillance missions. These devices have numerous
challenges, including energy consumption and unstable communication with
remote servers. Recent works [204, 137] proposed to avoid remote AI inferences
and leverage the computation capacity of ground robots to accomplish the
predictive tasks. However, existing works did not cover the distribution of
the inference among flying drones, characterized by their faster navigation,
higher power consumption, and ability to reach areas with high interferences
(e.g., high-rise buildings) compared to ground devices. Moreover, recent
efforts did not cover the path planning for different moving robots to
complete their assigned missions, while performing latency-aware predictions.
More specifically, the time period between capturing the data to the moment
when tasks from all the points are collected, should be minimized by
optimizing the devices’ trajectories, and planning close paths for
participants handling subsequent segments. Furthermore, the trajectories of
devices with available resources should cross the paths of the nodes
offloading the tasks, because of resource constraints.

####  VII-B4 Remote inference of non-sequential DNN models

A major part of pervasive inference literature analyzes the remote
collaboration, where the source device computes the shallow layers of the
model, while the cloud handles the deep layers. In this context, the split
point is chosen based on the size of the shared data, the resource capability
of the end-device, and the network capacity. This DNN partitioning approach
may work well for the standard sequential model, where filters are
sequentially reducing the size of the intermediate data. However, state-of-
the-art networks do not only include sequential layers with reduced outputs.
Indeed, generative models (GAN) [74] proved their efficiency for image
generation, image quality enhancement, text-to-image enhancement, etc. Auto-
encoders also showed good performance for image generation, compression, and
denoising. These types of networks have large-sized inputs and outputs. Hence,
despite the reduced intermediate data, the cloud servers have to return the
high-sized results to the source device, which implies high transmission
overhead. Another family of efficient neural networks is the RNN (see section
III-A1), used mostly for speech recognition and natural language processing.
These networks include loops in their structures and multiple outputs of a
single layer, which imposes multiple communications with remote servers in
case of partitioning. Other complex DNN structures prevent remote
collaboration wisdom, such as the randomly wired networks and Bolzman Machines
(BM) having a non-sequential dependency. Keeping up with ever-advancing deep
learning designs is a major challenge for per-layer splitting, particularly
for remote collaboration. Based on these insights, the scheduling of DNN
partitioning should have various patterns depending on the model structure.

####  VII-B5 Fault-tolerance of distributed inference

When a deep neural network is split into small segments and distributed among
multiple physical devices, the risk of nodes failure is increased, which leads
to performance drop and even inference abortion. The typical networking wisdom
resorts to re-transmission mechanisms along with scheduling redundant paths.
These failure management techniques inevitably consume additional bandwidths.
The DNNs are characterized by a unique structure that may enclose skip
connections, convolutional neural connections, and recurrent links. These
features of state-of-the-art networks implicitly increase the robustness and
resiliency of the joint inference. More specifically, skip blocks allow
receiving information from an intermediate layer in addition to the data fed
from the previous one. These connections, serving as a memory for some DL
models (e.g., ResNet), can play the role of fault-tolerant paths. If one of
the devices fails or leaves the joint system, information from a prior
participant can still be propagated forward to the current device via the skip
blocks, which adds some failure resiliency. The skip connections proved an
unprecedented ability to enhance the accuracy of deep models, in addition to
its potential to strengthen the fault-tolerance of pervasive computing.
However, transmission overheads are experienced, particularly for failure-free
systems. Thus, a trade-off between accuracy, resilience, and resource
utilization should be envisaged. Another vision to be investigated is to train
the system without skip connections and use them only in case of failures.
This idea is inspired from the Dropout [305] technique that is used to reduce
the data overfitting problem. It is based on randomly dropping some neurons
during the training and activating them during the inference. Studying the
impact of cutting off some transmissions during the inference for different
splitting strategies while re-thinking the dropout training is interesting to
strengthen the fault-tolerance of pervasive computing. Very recent works [168,
306] started to discuss such insights; however, they are still immature.

####  VII-B6 Data-locality-aware algorithms

Most of the efforts, studying the pervasive inference, focus on splitting and
parallelizing the DNN tasks related to a predictive request. Next, based on
the requirements of these tasks and the available resources in the joint
system (e.g., computation and energy), tasks are distributed and assigned to
the participants. However, in terms of memory, only the weight of the input
data is considered, whereas the weights to store the DNN structure are never
taken into account. In section III, we showed in Table 2 that state-of-the-art
DNN models are very sized and require high memory availability. For example,
VGG-16 model has 138 M parameters and requires 512 Mb to store its filters.
What worsens the situation is that some partitions impose copying the filters
to all participants (e.g., spatial splitting.). Moreover, if the intelligent
application is led by multiple DNN models and different segments are assigned
to each device, a huge memory burden is experienced. Therefore, data-locality-
aware algorithms should be designed. More specifically, the distribution
system has to account for the past tasks assigned to each participant and try
to maximize the re-usability of previously-stored weights, with consideration
to the capacity of the devices. Minimizing the number of weights assigned to
each participant, not only contributes to reduce the memory usage, but also
guarantees the privacy of the structure against white-box attacks [307].

####  VII-B7 Pervasive inference for nanotechnology applications

Nanotechnology is the field of innovation and research that focuses on
creating particles (e.g., devices and materials) in the scale of atoms. These
particles can be used in multiple domains, such as Nanomedicine that studies
new ways of detecting and curing diseases. One of the interesting examples of
Nanomedicine is the detection of diabetes through analyzing human’s breaths.
In fact, our body chemistry and our breaths change when we are sick, although
our noses are not strong enough to detect it. More specifically, specific
biomarkers are released in case of sickness, giving a huge opportunity to
detect the disease just by sniffing out the breath. However, a big challenge
is faced, as these biomarkers exist at a very low concentration equal to
parts-per-million (ppm). In the context of diabetes, Acetone is produced such
as patients have 2 ppm Acetone concentration, whereas healthy people have only
1 ppm. Meaning, the difference of the biomarker concentration between healthy
and patients is equal to 1 ppm. In order to detect this ppm or even part-per-
billion (ppb) in the human breath rather than blood, the design of super-
sensitive sensors is mandatory. Before nanotechnology, it was not possible to
precisely detect such nano concentration. Nowadays, intelligent and invisible
nano-sensors can be trained to sniff human breath. However, reaching the full
potential of Nanomedicine (e.g., drug delivery systems and precision cancer
medicine) is still yet to be fully realized.

To guarantee that Nano particles achieve the targeted objectives, large amount
of data and computational analysis is expected. While the traditional
techniques opt for an in-depth understanding of biological and chemical
knowledge, the AI only requires data training. Thus, it is highly interesting
to integrate the AI to evaluate and formulate the nanoscale particles [308,
309]. However, these particles suffer from small energy capacity that limits
their communication with remote devices (e.g., handheld mobiles and
computers). Hence, the distribution of inference within the nano-sensors can
provide localized processing and minimize the data transmission. In this
context, new partitioning strategies should be envisaged, as the existing ones
do not fit the extremely limited computational resources of the particles.
Particularly, even neuron, spatial, or filter splitting involving numerous
multiplications are considered complex tasks. Thus, per-multiplication
partitioning and the related dependency between millions of nano-participants
have to be investigated to ensure the practicality of this futuristic
convergence between pervasive AI and nanotechnology.

###  Enhanced federated learning algorithms

####  VII-C1 Active Federated Learning

Given the main limitations of FL in terms of communication overheads and slow
convergence, combining AL concept with emerging FL schemes would be of great
interest. Since most of the existing schemes for FL suffer from slow
convergence, a novel active FL solution would be needed, which exploits the
distributed nature of FL, while coping with highly dynamic environments and
ensuring adequately fast convergence. Indeed, heterogeneity of the local
training data at distributed participating nodes and considering all nodes in
the FL process can significantly slow down the convergence. Full nodes
participation renders the centralized server to wait for the stragglers. Thus,
we envision that: (1) exchanging some side information between different
participating nodes (e.g., the unique data samples or class distribution) can
significantly help in tackling the data heterogeneity problem; (2) considering
partial node participation by proposing efficient user selection schemes can
play an important role in decreasing communication overheads and accelerating
the convergence.

####  VII-C2 Blending inter and intra data parallelism for federated learning

Deep neural networks require intensive memory and computational loads. This
challenge is compounded, when the model is larger and deeper, as it becomes
infeasible to acquire training results from a single resource-limited device.
Triggered by this challenge, federated learning is proposed to train deep
models over tens and even hundreds of CPUs and GPUs, by taking advantage of
inter-data parallelism. At present, federated learning techniques split the
data to be trained among pervasive nodes while copying the whole DL model to
all of them. Still, small devices cannot participate in such a process due to
their limited capacities. Hence, blending the inter-data parallelism where the
trained data is distributed and the intra-data parallelism where the
intermediate data and segments of the model are partitioned, can be a feasible
solution to enable training within non-GPU devices. Certainly, the
practicality, gains and bottleneck of such an approach are to be examined and
studied, as the backpropagation characterizing the training phase imposes huge
dependency and communication between devices.

###  Communication-efficient online learning

####  VII-D1 Demonstrated applications

Since most of the MAB algorithms discussed in this paper are recent, it
remains interesting to see their implications on practical applications. For
example, quantifying the effect of bounded communication resources or energy
used in wearable devices and congestion between edge nodes. Similarly,
quantifying the improvement in regret bounds on actual and Quality of
Experience (QoE) metrics can be promising.

####  VII-D2 More general forms of MABs

The state of art algorithms in the distributed and federated setup adapt the
finite-actions, and the stochastic case of the multi-agent settings. However,
there exist many more general forms of the bandit problem that are yet to be
studied under the multi-agent settings. These include but are not limited to
adversarial-bandits, linear bandits, pure exploration, and non-stationary
bandits. Investigating potential regret improvements and communication
resource utilization in the MAB settings of non-stochastic and infinite-action
bandits remains to be tackled.

####  VII-D3 Heterogeneity of Bandit agents

In MAB settings, agents might not only differ in the instance each is trying
to solve, but also in their computational capabilities. Different
computational capabilities mean that agents interact with their environments
at different rates, collecting an additional amount of samples and hence
different quality estimates. While the effect of this computational
heterogeneity is heavily studied in supervised federated learning, it is not
yet investigated either in distributed or federated bandits.

####  VII-D4  MARL performance/communication tradeoff

Methods that train in a logically centralized server and then execute in a
decentralized manner (CTDE) are able to communicate less (even not at all) at
execution while being able to learn good joint policy due to the central
training phase, as illustrated earlier. However, their adaptability is not
guaranteed when dealing with a non-stationary environment, and they might