Peer Offloading with Delayed Feedback in Fog Networks

In recent literatures, quite a few computation offloading problems over the fog networks have been proposed. The authors in [6] investigated the computation offloading problem by adaptively offloading the computation tasks from cloud to fog servers with the predicted mobility. The task offloading problem was formulated as a multi-period generalized assignment problem in [7], which aimed at minimizing the total delay by offloading tasks to suitable fog nodes in each period. The work in [8] studied a workload assignment problem between fog and cloud that considered the trade-off between power consumption and transmission delay. The above studies are based on centralized scheduling with high overhead of information exchange at edge devices. Such offloading algorithms do not fit for real-time and massive data services. In addition, these studies do not consider the offloading among FNs, which can be more challenging with unbalanced workload among FNs.

To tackle the peer offloading problem, the authors in [9] and [10] formulated the offloading problem as a convex optimization problem to minimize the energy consumption with latency constraints. In [11], a latency minimization problem was studied to allocate the computation resources of the edge servers. Meanwhile, the authors in [12] proposed a task allocation approach that minimized the overall task completion time using a multidimensional auction. In the above works, it is generally assumed that information of the fog network is completely known, thus the computation offloading is modeled as a deterministic scheduling problem. However, such assumptions do not hold in practice since the global information could not be obtained in real-time and the network status may change rapidly.

For the task offloading problem with unknown dynamics, the authors in [13] proposed an online peer offloading algorithm for time-varying channel conditions and stochastic arrival tasks. The work in [14] proposed an online secretary algorithm to minimize the offloading latency with unknown arrival rates of neighboring FNs. The latency, the energy consumption, and the switching cost were jointly considered as a stochastic programming problem in [15]. Taking into account the requirements of ultra-reliable low-latency, the authors in [16] proposed a mechanism to minimize the users’ power consumption while considering the allocated resources. Besides, in [17], the workloads of neighboring FNs were formulated as a Markov model and a latency minimizing algorithm was proposed to track these dynamics. These works assume that the workload of FNs satisfies some stationary distributions. Furthermore, there exist competition and collision effects among other FNs offloading choices. Some unexpected tasks brought by dynamic network structure and conditions could deteriorate the offloading performance.

In general, all works mentioned above assume instantaneous feedback of offloading decisions. The task assigner is assumed to receive the expected latency when the tasks are dispatched. This assumption is not always valid in the real world since the FN that provides computation ability may not be able to give accurate latency estimates when the tasks are received. The exact execution clock cycle of each task can not be obtained until it is finished. The execution time of a task is coupled with the hardware and the software state, such as, the cache condition, resource contention, scheduling policy, interrupt management, etc. In fact, even the measurement of the worst-case execution time (WCET) of a task is quite a headache problem in the field of real-time operating system (RTOS) [18].

In this paper, for the FN who wants to offload tasks, we assume that: (1) the global FNs state information is not known; (2) the resources of service FNs may be unpredictably competed by other FNs; (3) the offload feedback is obtained only when the task was processed and finished by the computation FN. These assumptions naturally raise three challenging problems. Firstly, the performance achieved from each FN is unaware beforehand and has to be learned due to dynamic FN conditions. Secondly, the achieved performance also depends on the set of competing tasks, which is unpredictable since the decisions of other FNs are made locally without coordination. Thirdly, the feedback of the offloaded task is delayed, which may deteriorate the achieved performance of existing strategies. Most algorithms for computation offloading do not fully consider the uncertainties mentioned above and are not in favor of these assumptions.

In [19], we studied the computation peer offloading problem in a fog-enabled network. Our goal is to minimize the peer offloading latency in uncertain environment without instantaneous latency feedback. An exponential based algorithm was proposed to handle the tricky problem and simulation results revealed the efficiency of the proposed strategy.

In this paper, we extend our previous work with theoretical proofs for the single-agent setting in [19]. Furthermore, we study the computation peer offloading problem for the multi-agent setting. The main contributions of this paper are summarized as follows.

• •

  We develop an online learning framework for fog networks, where each FN can offload their computation tasks to peer FNs in the vicinity. We formulate the latency minimization problem as a sequential decision making problem. Both single-agent and multi-agent settings are considered in this work.

• •

  For the single-agent setting, an online learning algorithm is advocated based on the adversarial multi-armed bandit (MAB) framework, which accommodates arbitrary variation of FN conditions. The proposed method can be harnessed to learn the statistical information of the network through delayed information feedback. Besides, the proposed method allows task dispatching FN to dynamically identify the most suitable service FNs without the prior knowledge of arrival tasks and channel conditions. The theoretical proof is provided, suggesting that the proposed algorithm achieves a sub-linear order with delayed feedback.

• •

  For the multi-agent setting, we consider the different conflict resolutions when multiple tasks are dispatched to the same FN. Assume that all FNs adopt the same strategy, multi-agent setting can be regarded as a game between an FN and the rest of FNs. The proposed algorithm for the multi-agent setting can achieve the same optimality performance as the single-agent setting. Besides, the proposed algorithm tailored for the offloading game can converge to an $\epsilon$-NE in a specific two users setting.

The rest of the paper is organized as follows. The system model and optimization problem are introduced in section II. An online learning algorithm for computation offloading with delayed feedback is proposed in section III. The theoretical analysis of multi-agent games with the proposed algorithm is studied in IV. Numerical results are given in section V and section VI concludes our work.

Consider a fog network consisting of an end-user layer and a fog layer as shown in Fig. 1. In our framework, the end-user layer includes smartphones, laptops and wireless sensors that do not have enough computation capability and are power limited. With the help of fog computing, these end-users can offload their task data to the fog layers for remote distributed computing purposes. We consider a fog network with $N$ FNs, defined by $\mathcal{N}=\{1,2,...,N\}$. Each FN can process the task from end-user devices or other peer FNs, which is typical in practical fog networking [20].

For concisely, we classify FNs into the following two categories: (1) Task FN: An FN is a task FN if it offloads workloads to other FNs. Moreover, it does not receive any workload from other FNs; (2) Service FN: An FN is called a service FN if it receives workloads from other FN and does not offload workload to others. Let $V$ and $K$ denote the amounts of task FNs and service FNs in fog networks. Notice that in our categorization, a smart FN won’t offload workloads to other FNs while receiving workloads from other FNs. In other words, the FN can only play a role in the task FN and the service FN.

The operational timeline is discretized into time slots (e.g., $10$ ms) for making peer offloading decisions. Once FN $i$ receives $b_{t}^{i}$ task at time slot $t$, the FN can process the task locally or offload the task to its neighboring FNs. The service rate, which denotes the expected number of consecutive task completions per time slot, can help character the computation capability of FN. Intuitively, the FNs with low service rates or their central processing units (CPUs) are running at full load prefer to offload computation tasks to its neighboring FNs, while the FNs with high service rates or abundant idle computation resources prefer to process locally.

Next, we discuss the latency of peer computing and local computing, which is our foremost concern. The latency of peer computing contains three parts: (1) latency of task dispatching; (2) latency of task processing; (3) latency of results receiving. The latency of results receiving can be negligible due to the relatively small size of computation results [21].

Most works about computation offloading assumed that some prior information is available, such as, wireless channel state information (CSI) [22, 23]. However, it is not easy to have access to such information, especially when the number of FNs is large. In this paper, CSI is assumed to be time-varying and unknown before task transmission. Task FN $i$ can offload tasks to service FN $j$ over a wireless channel. The transmitted rate can be given by

where $g^{ij}$ is the channel gain between FN $i$ and $j$, and $h$ is the average fading gain of the FN $i$. Notation $P^{i}$ is the transmission power of FN $i$ and $\sigma^{2}$ denotes the noise power spectral density. The bandwidth per node is the same in our model and is given by $B$. We denote $\overline{r}^{ij}$ as the average transmission rate between FN $i$ and FN $j$ during one task transmission. Thus the task dispatching latency can be described as

The channel deterioration may lead to the failure of the computation tasks’ transmissions. The task FN can confirm the transmission status by acknowledgement (ACK) or negative-acknowledgement (NACK) message [24]. Once receiving a NACK message, the task FN will re-transmit the task with the Automatic Repeat-reQuest (ARQ) or the Hybrid Automatic Repeat-reQuest (HARQ) scheme [25].

The majority of existing offloading studies consider an ideal setting that the task FN can obtain the computation latency when tasks arrive at the service FN. However, current OSs do not support instantaneous feedback. The initial machine state of the service FN varies before the task executes and some interrupts may occur during the computation processing. In this paper, the feedback latency can be obtained when the service FN finishes the execution of the offloaded task.

Next, we define the computation model in the service FNs. According to Kleinrock approximation [26], the arrival process of the task can be regarded as a Poisson process. To model the perturbation of the computation process in service FNs, the service rate of each FN is assumed to be negative exponentially distributed (i.e., generated by a Poisson process). Besides, the statistics of arrival rates vary among FNs since the density of end-users is usually not uniform. The arrival rate $\lambda$ of an FN is unaware to other FNs.

When a task arrives at the destination, it will be cached in the queue if the service FN is busy. Since the computing service rate $\mu_{t}^{j}$ of FN $j$ at time slot $t$ may be perturbed by some system interrupts, we assume that $\mu_{t}^{j}$ is unknown to all FNs. Let $\bar{\mu}_{t}^{j}$ denote the average service rate during computation. The computation queue can be modeled as an $M/M/1$¹¹1$M$ denotes Markov property. queue. An $M/M/1$ queueing system indicates that the tasks arrive according to a Poisson process and the service rates are assumed to be independent and exponentially distributed. This is consistent with what we described earlier. Let $Q_{t}^{j}$ denote the current task queue length of FN $j$ when the task arrives at time slot $t$.

Without loss of generality, we assume that the task computation latency in service FNs is proportional to the received task size, such as, $kb_{t}^{i},k\in R^{+}$. Thus, the computation latency at FN $j$ is

Equation (3) denotes an estimation of the computation latency.

Combining the communication latency and computation latency, the total peer offloading latency is

In practice, the offloading latency can not be infinite, we bound it within $[0,T_{\text{max}}]$, where $T_{\text{max}}$ is the maximal tolerable latency. Thus, the loss $l_{t}^{j}$ of each choice is described as

where $l_{t}^{j}\in[0,1]$. We want to minimize the average latency of each FN in the long term and it can be formulated as

where $I_{t}$ denotes the index of the offload FN at time slot $t$, $\mathcal{I}$ denotes the set of all the offloading choices and $\mathbbm{1}$ represents indicating vector. In our model, the channel conditions and task queues of the service FNs are unaware to the task FN. The task FN could not receive the latency results until the feedback has been received. Finding the optimal solution of (6) is challenging with the non-realtime information.

Online learning is a well-established paradigm for making a sequence of decisions when given the knowledge of previous prediction feedback. Besides, online learning can reduce computation complexity and has been investigated in many literatures. Integrating online learning scheme, the challenging optimization problem of (6) can be converted into the low-complexity sequential decision problem at each time slot.

Vanilla online learning algorithm operates in a fixed order, such as making choices, receiving feedbacks and updating the learning model. These typical online learning algorithms may not work under the delayed feedback setting, where the order of the received feedback may not be in line with the order of the dispatches. The lag of the feedback and disorder of the observations bring significant challenges to vanilla online learning algorithms.

The adversarial MAB is an efficient algorithm when engaged in the dynamic environment. The offloading problem in section II can be modeled as an adversarial MAB consisting of a set of players (task FNs), which can choose an action (service FN) from the action sets (available service FNs). When the task FN makes a choice at time slot $s$, the offloading loss can be observed by the task FN after $d_{s}$ time slots. The action of offloading is adopted by one FN at slot $s$ and the loss is obtained at slot $t$, so we have $s+d_{s}=t$.

To measure the utility of the task offloading scheme $\Phi$, the concept of expected regret is introduced. Expected regret is harnessed to distinguish the cumulative loss of $\Phi$ and the best strategy in hindsight. The desired $\Phi$ is to minimize its expected cumulative regret $R_{\Phi}(T)$, which is defined as

where $\mathbb{E}(\cdot)$ represents the expectation operation, $a\in\{1,...,K\}$ denotes the action and $A$ denotes the best policy which gives the least loss. Notation $l_{s|t}^{a}$ represents the loss introduced by the time lag and $l_{t}^{A}$ denotes the loss of optimal policy $A$.

In adversarial multi-arm bandit setting, task FN chooses service FN $j$ using the mixed strategies according to a probability distribution $\bm{p}_{t}=[p_{t}^{1},p_{t}^{2},...,p_{t}^{K}]$ [27]. Due to the variation of computation lag, the result computation latency may be observed in a disorderly manner. We then introduce an algorithm to handle the delayed feedback and make the decision for task offloading.

Let $\mathcal{L}_{t}$ denote the arrival feedback set at time slot $t$ and $|\mathcal{L}_{t}|$ denote the size of feedback set. Recall that the feedback at slot $t$ includes losses incurred at slot $s$. Once $\mathcal{L}_{t}$ is revealed, the FN can get the estimated loss according to $\bm{p}_{t}$ at the current slot. For each $l_{s|t}^{j}\in\mathcal{L}_{t}$, a biased estimator $\tilde{l}_{s|t}^{j}$ for reducing the estimation variance of the loss vector is

where $\beta$ is the biased factor of the loss for implicit exploration[28].

During a time slot $t$, the task FN may collect more than one feedback or without any feedback. Once receiving the feedback, it will be buffered and then updates $\bm{p}_{t+1}$ at the beginning of slot $t+1$. If the offloading feedback is returned in $[0,d_{\max}]$, we regard it as an efficient offloading action. On the other hand, if $d_{s}\geq d_{\max}$, the task FN regards the action as a failure because of the intolerable latency. Here, the task FN updates $\bm{p}_{t}$ with loss $l_{s|t}=1$. The computation task will be re-offloaded after $d_{\max}$ according to the selection probability. For $l_{s|t}^{i}\in\mathcal{L}_{t}$, the task FN $i$ updates the weights and probabilities of all service FNs with

where $\eta$ denotes the step size. If $\mathcal{L}_{t}=\emptyset$, the task FN directly reuses the previous distribution, i.e., $\bm{p}_{t+1}=\bm{p}_{t}$, and the offloading strategy does not change at all. When the feedback is received without lag, the updating scheme of the proposed algorithm is similar to the vanilla EXP3-IX algorithm [28].

Algorithm 1 summarizes the proposed DEB algorithm for processing the task offloading problem with delayed feedback. Initially, the probability of each FN is set as $1/K$. The task FN makes the offloading choice according to the probability distribution $\bm{p}_{t-1}$. If fresh feedback arrives, the task FN calculates the estimated loss and updates the weight of each service FN. If not, the task FN makes the decision according to the previous distribution.

In this part, we analyze the regret of the proposed delayed exponential based algorithm.

According to Theorem 1, the regret of the proposed algorithm can be upper bounded by sub-linear order with determining proper update parameters. This result indicates that the regret growth decreases as time goes by, yielding the optimal service FN selections of the proposed algorithm.

In the multi-agent setting, there are $V$ active task FNs and $K$ independent service FNs. In our paper, a time slot is divided into sub-slots. The $V$ task FNs are allocated to access $K$ service FNs in each sub-slots. In most cases, this assumption holds since not all task FNs are active to offload tasks at the same time. At each time slot, each active task FN chooses one service FN to offload its computation tasks based on its local observations. In addition, task FNs do not share information with each other due to the consideration of information security. In our framework, the different task FNs access service FNs in a time-division manner. Collisions occur when multiple task FNs choose the same service FN. Two collision models are considered in our paper. One is the ‘winner-takes-all’ model when a collision occurs. In this model, the computation task of one task FN is processed and the rest would not be processed. The other model is that the service FN accepts all the arrival tasks and arranges the arrivals in a random manner in the queue without jumping. In the multiple task FNs setting, the total reward under a policy $\Phi$ by time $t$ is the same as (7), which is given by

where $l_{s|t}^{a}(v)$ denotes the loss of task FN $v$. The regret derivation procedure of the proposed algorithm in multiple agents setting is the same as the single case and here we care more about the NE property of the proposed strategy.

An NE is a set of strategies, one for each of multiple players of a game, that each player’s choice is his best response to the choices of the other players [30]. Besides, the NE has the self-stability property such that the users at the equilibrium can achieve a mutually satisfactory solution and no user has the incentive to deviate. In the multi-agent decentralized offloading scenario, an NE means no task FN has an incentive of changing its mixed strategy if all other FNs do not change their strategies. This property is crucial to the decentralized computation offloading problem, since the task FNs may act in their own interests. For each task FN, achieving an NE means the current strategy is their optimal response, thus yielding a minimal latency solution.

In the following discussion, we will concentrate on investigating the NE property of the proposed algorithm. We investigate the NE property of the proposed algorithm in a two users zero-sum case.

Let $U$ be the cost matrix, such that when the row player plays $i$ and the column player plays $j$, the former pays a cost of $U(i,j)$ and the latter gains a reward of $U(i,j)$ (a.k.a., a cost of $-U(i,j)$), where $0\leq U(i,j)\leq 1$ for any $i,j$. Notation $\bm{p}_{t},\bm{q}_{t}$ represent the mixed strategies of row player and column player, then we use the convention that

and

NE is a critical concept in game theory to predict the outcome of a game. An NE is a strategy profile $(\bm{p}_{t}^{*},\bm{q}_{t}^{*})$ such that there is no motivation for any player to change its strategy since the changed strategy will degrade the benefit. To obtain the desired strategy, we need to define the set of all approximate NE:

The entity that converges to the set of NE in our case is the ergodic average of $(\bm{p}_{t},\bm{q}_{t})$.

The main theory analysis, given in Theorem 2, generalizes this statement for the case with delayed feedback, and the proposed algorithm can converge to an NE with the feedback lag. Note that the convergence of the ergodic mean to the set of NE is in the $L1$ norm sense, which is much stronger than the convergence of the expected ergodic mean.

Regarding the action of the adversary as the multiple merged actions of other players, the two players setting can be generalized to the multiple players setting [31].

In the first part, we would like to exam the performance of the DEB algorithm in the single-agent setting. Consider a fog network consisting of $7$ FNs. The number of task FN is $1$, and the rest are service FNs. The task FN is deployed in the center of a circle with $2$ km radius, where the service FNs are randomly deployed in this range. In particular, the path-loss channel is generated according to the 3GPP propagation environment [24]. The total time slot $T$ is set as $30000$. Besides, to perform the dynamic computation perturbation, the service rates $\mu$ of FNs follows the Poisson distribution with mean generated from the Gaussian distribution with $\mathcal{N}(6,1)$. To normalized the offloading latency, we set $T_{\max}$ as $5$. The threshold $t_{\max}$ that prevents the delay of feedback from being too large is set as $3$.

In fog computing, to the best of our knowledge, there does not exist any literature considering delayed information feedback. To evaluate the performance of the proposed algorithm, we compare the performance of the proposed DEB algorithm to the following schemes that can be implemented in the delayed feedback setting. (i) Queued Partial Monitoring with Delayed Feedback (QPM-D) algorithm [32]: the feedback of each offloading decision is assigned to the queue corresponding to the selected service FN and the feedback information is employed when the service FN is chosen; (ii) Stochastic Delayed Bandits (SDB) algorithm [33]: an algorithm that combines the QPM-D for the main updated scheme and a heuristic scheme for controlling the sampling distribution to improve performance in the presence of delay; (iii) Delayed Upper Confidence Bound (DUCB) algorithm [34]: an algorithm that exploits the delayed feedback to adjust the reward update in classical UCB framework; (iv) Bandit Learning-based Offloading of Tasks (BLOT) algorithm [15]: an offloading algorithm that selects the service FNs by means of the currently available information; (v) Non-delayed offloading: each task FN receives the feedback instantly using the Exponential-weight algorithm for Exploration and Exploitation (EXP3) algorithm presented in [27]. Here QPM-D and SDB are meta schemes for handling delayed feedback. Besides, we adopt Thompson sampling algorithm for the implementation of the QPM-D and SDB algorithm. Note that the BLOT algorithm is not designed for the latency minimization problem, a little bit modification is taken to make BLOT work in this system setting.

In the first experiment, we consider a stationary setting in which the arrival rates of task FNs are constant over time. The arrival rates of FN $i$ is set to be $\lambda_{i}=4.5+0.5\times i$ , suggesting that the FN $1$ achieves the best delay performance in statistics. In Fig. 2, we plot the regret performance, latency performance and the task FN selections of the DEB, QPM-D, SDB, DUCB, BLOT and non-delayed EXP3 algorithms. In addition, the latency of optimal choice (task FN always selects service FN 1) has been plotted to show the performance gap of the above algorithms. Here $1000$ Monte Carlo simulations are performed.

Fig. 2 (a) depicts the regret performance of offloading decisions with the above algorithms. The $y$-label of the figure represents the ratio of the aggregate regret, revealing the regret order of the DEB, QPM-D, SDB, DUCB, BLOT and non-delayed EXP3 algorithms. The convergence performance of the proposed algorithm represents the learning process of the environment, such as the channel condition and the computation capacities of neighboring FNs. From Fig. 2 (a), we observe that the DEB algorithm achieves better regret performance than the QPM-D, DUCB, BLOT and SDB algorithms. The discrepancy of the performance between DEB, QPM-D, SDB algorithms is caused by the utilization of delayed feedbacks. The proposed DEB algorithm harnesses the delayed feedbacks instantly. The QPM-D and SDB algorithms store the delayed feedbacks of a service FN to its queue firstly and update when the service FN is selected. Due to the delayed feedback, such updating schemes will degrade the regret performance. As for the performance gap between the DUCB, the BLOT and the DEB algorithms, the DUCB and BLOT algorithms focus on the recent feedback but loses sight of the entire information, which results in a larger performance loss. Without the knowledge of other FNs’ conditions and peer competitions, the FN adopted the DEB algorithm can always adapt to the environment and make a proper choice.

Fig. 2 (b) indicates the average offloading latency of the single-agent setting. The offloading latency of the QPM-D and SDB algorithms decrease fast at the beginning and achieves sub-optimal latency performance later. Moreover, the converged latency of algorithms DUCB and BLOT perform not as well as the DEB algorithm. The reason comes from that the DUCB and BLOT algorithms adopt the discount UCB style to handle the delayed feedback. Thus the exploration procedure pay more attention to the recent feedback. Thus the two algorithms are not sufficient to identify the best service FN. The proposed algorithm can fully explore the service FNs and then pick the best FN, thus revealing a better averaged latency performance. This figure can also be leveraged to complementary explain the results in Fig. 2 (a).

In Fig. 2 (c), the statistical selections of DEB, QPM-D, SDB, DUCB, BLOT and EXP3 algorithms are depicted with the same simulation setup. According to the simulation setup, FN $1$ has the smallest expected loss and FN $6$ has the largest expected loss. Fig. 2 (c) reveals that the task FN selects the best FN for the most times with the DEB algorithm. For the FN with the largest loss, the task FN rarely offloads tasks to it and its selections occur during the exploration period for most of the time. Combining the three figures of Fig. 2, we can conclude that the DEB algorithm can better adapt to the changeable environment compared to other algorithms, thus yielding the smallest regret.

In the second experiment, the performance of the proposed algorithm in dynamic changing network environment is verified. In the first $T/2$ time slots, the arrival rates of FN $i$ is set as $\lambda_{i}=4.5+0.5\times i$, which is the same as the first experiment. In the last $T/2$ time slots, the arrival rate of FN $1$ slows to $7$, then the FN $2$ starts to outperform FN $1$ and eventually becomes the leader. The above setting is more practical where the arrival rates of FNs may change due to the dynamics of the network structure. This experiment can exam the robustness of the proposed algorithm.

In Fig. 3, we explore the average latency performance of the DEB, QPM, DUCB, BLOT and SDB algorithms in the dynamic setting. Here $1000$ Monte Carlo simulations are performed. From Fig. 3, we observe that the performance tendencies of all the algorithms have changed at $T/2$ as the network statistic varies. Then the deteriorated performance recovers eventually in the rest time. Contrasting with QPM-D, SDB, DUCB and BLOT algorithms, the DEB algorithm recovers faster when task FN suffers network statistic variation, suggesting a more robust property. It is because the DEB algorithm selects the service FNs according to a probability distribution, and the implicit exploration factor $\beta$ can help adapt to the dynamic environment.

To evaluate the scalability of the DEB algorithm, we exam the latency performance of the DEB algorithm with different network sizes in Fig. 4. Here the number of service FNs are set as $K=\{20,100,500,1000\}$. The FN $1$ is set as the best service FN with arrival rate $5$, while the rest service FNs are uniformly generated from $[6,10]$. From Fig. 4, we observe that the latency performance deteriorates with the increment of task FNs. Additional service FNs add the cost of exploration, which results in worse average latency. However, as time goes by, the average latency decreases. The task FN with the DEB algorithm can pick the best service FN eventually.

In this part, we investigate the performance of the proposed algorithm in the multi-agent setting. We set $V=4$ and $K=10$. The arrival rate of each FN $i$ is set as $\lambda_{i}=4+0.4\times i$. In the multi-agent scenario, the DUCB and BLOT algorithms cause severe collisions in its exploration stage, thus the two algorithms are not applicable to multi-agent setting. Thus, we only compare the performance of the DEB, QPM and SDB algorithms here.

Fig. 5 explores the multi-agent performance of the DEB, SDB and QPM algorithms. Here we adopt a weak-collision setting, where the service FN processes the multiple arrivals in a random order manner. In this setting, the task FNs suffer slight collision loss when there exist multiple arrival tasks in service FN. Fig. 5 plots the average latency of different users with the above algorithms. Compared to the SDB and QPM algorithm, the DEB algorithm performs worse in the beginning, then gets better as time goes by. The DEB algorithm chooses service FNs according to the probability distribution, indicating a sufficient exploration for all service FNs. Such selection rule is more suitable for dynamic Markov environment. In addition, Fig. 6 shows the service FNs selections of the DEB algorithm for different agents. From Fig. 6, we observe that the service FNs with low arrival rates are nearly equally selected by the four agents. In this setting, the loss caused by collisions is slight. Therefore, the agents prefer to share the best FNs when the offloading strategy becomes stable.

In the next experiment, we investigate the performance of the DEB algorithm in a ‘winner-takes-all’ setting, where only one task FN can obtain the real loss and the rest suffer the total loss $1$. To reveal the NE property of the proposed algorithm, here we only consider $2$ agents. The number of service FNs is set as $6$. The arrival rate of service FN $i$ is set as $[4,4,5,6,7,8]$. It can be observed that the NE points in this setting is: (i) task FN $1$ chooses service FN $1$ while task FN $2$ chooses service FN $2$; (ii) task FN $1$ chooses service FN $2$ while task FN $2$ chooses FN $1$. Fig. 7 reveals the task FNs’ selections during period [0,$\frac{T}{3}$], ($\frac{T}{3}$,$\frac{2T}{3}$], ($\frac{2T}{3}$,$T$] and $[0,T]$, respectively. In the earlier stage of offloading, the two task FNs prefer to share service FN $1$ and FN $2$. However, it will result in many collisions when their choices are the same. After suffering the performance loss from collisions, the two agents become smarter and gradually avoid selecting the same FN. Eventually, both the two task FNs achieve the NE point, where task FN $1$ choosing service FN $2$ and task FN $2$ choosing service FN $1$. This simulation result indicates that even with delayed feedback, the proposed algorithm can converge to an NE in the ergodic average sense.